Algorithms/prime factors

تحليل العدد إلى عوامله الأولية يعني إيجاد الأعداد الأولية التي يكون حاصل ضربها ببعضها مساويًا للعدد الأصلي.

يمكن إيجاد العوامل الأولية لعدد معين n باتباع الخطوات التالية:

1. إذا كان العدد المعطى يقبل القسمة على 2، فنطبع العدد 2 ونقسم n على 2.
2. بعد الخطوة الأولى تصبح n عددًا فرديًا، لذا سنستخدم حلقة تكرارية تبدأ من i = 3 وتنتهي عند الجذر التربيعي للعدد n. ما دام العدد n يقبل القسمة على العدد i، فسنطبع العدد i ونقسم n على i، ونزيد قيمة i بمقدار 2 وتستمر الحلقة التكرارية.
3. إن كان n عددًا أوليًا أكبر من n، فإنّنا لن نصل إلى العدد 1 باستخدام الخطوتين السابقتين؛ لذا سنطبع العدد n إن كان أكبر من 2.

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

void primeFactors(int n) 
{ 
	// طباعة عوامل العدد المعطى من الرقم 2
	while (n % 2 == 0) 
	{ 
		cout << 2 << " "; 
		n = n/2; 
	} 

	// يجب أن يكون n فرديًا في هذه النقطة لذا يمكننا
	// تجاوز عنصر واحد
	// i = i +2 
	for (int i = 3; i <= sqrt(n); i = i + 2) 
	{ 
		
		// i إذا كان العدد المعطى يقبل القسمة على
		// i نقسم العدد المعطى على 
		// i ونطبع قيمة
		while (n % i == 0) 
		{ 
			cout << i << " "; 
			n = n/i; 
		} 
	} 
	// إذا كان العدد المعطى عددًا أوليًا أكبر من 2
	if (n > 2) 
		cout << n << " "; 
} 

/* اختبار الدالة السابقة */
int main() 
{ 
	int n = 315; 
	primeFactors(n); 
	return 0; 
}

• بايثون:

import math 

def primeFactors(n): 
	
	# طباعة عوامل العدد المعطى من الرقم 2
	while n % 2 == 0: 
		print 2, 
		n = n / 2
		
	# يجب أن يكون n فرديًا في هذه النقطة لذا يمكننا 
	# تجاوز عنصر واحد
	# i = i +2 
	for i in range(3,int(math.sqrt(n))+1,2): 
		
		# while i divides n , print i ad divide n 
		while n % i== 0: 
			print i, 
			n = n / i 
			
	# إذا كان العدد المعطى عددًا أوليًا أكبر من 2
	if n > 2: 
		print n 
		
# اختبار الدالة السابقة

n = 315
primeFactors(n)

• جافا:

import java.io.*; 
import java.lang.Math; 

class GFG 
{ 
	// A function to print all prime factors 
	// of a given number n 
	public static void primeFactors(int n) 
	{ 
		// طباعة عوامل العدد المعطى من الرقم 2
		while (n%2==0) 
		{ 
			System.out.print(2 + " "); 
			n /= 2; 
		} 

		// يجب أن يكون n فرديًا في هذه النقطة لذا يمكننا
		// تجاوز عنصر واحد
		// i = i +2  
		for (int i = 3; i <= Math.sqrt(n); i+= 2) 
		{ 
			// i إذا كان العدد المعطى يقبل القسمة على
			// i نقسم العدد المعطى على 
			// i ونطبع قيمة 
			while (n%i == 0) 
			{ 
				System.out.print(i + " "); 
				n /= i; 
			} 
		} 

		// إذا كان العدد المعطى عددًا أوليًا أكبر من 2 
		if (n > 2) 
			System.out.print(n); 
	} 

	public static void main (String[] args) 
	{ 
		int n = 315; 
		primeFactors(n); 
	} 
}

تتعامل الخطوتان الأولى والثانية مع الأعداد المركبة composite numbers، أما الخطوة الثالثة فتتعامل مع الأعداد الأولية.

تمتاز الأعداد الأولية بأنّها تمتلك على الأقل معاملًا أوليًا واحدًا يكون أصغر من الجذر التربيعي للعدد الأصلي أو أصغر منه.

يمكن إثبات هذه الخاصية كما يلي:

لنفترض أنّ العددين a و b هما عاملان للعدد n حسب العلاقة a*b = n. إن كان العددان أكبر من الجذر التربيعي للعدد n فإنّ a.b > √n, * √n وهذا يناقض التعبير a * b = n.