إيجاد قواسم عدد طبيعي

يمكن إيجاد قواسم عدد طبيعي (الأعداد التي يقبل القسمة عليها دون باقٍ) بطريقتين:

الطريقة البسيطة

الطريقة الأولى هي طريقة بسيطة وتعتمد على المرور على جميع الأعداد من 1 إلى n والتحقّق من كون العدد المعطى قابلًا للقسمة على هذه الأعداد، ثم طباعة النتيجة.

• C++‎:

#include <bits/stdc++.h> 

void printDivisors(int n) 
{ 
	for (int i=1;i<=n;i++) 
		if (n%i==0) 
			printf("%d ",i); 
} 

/* اختبار الدالة السابقة */
int main() 
{ 
	printf("The divisors of 100 are: \n"); 
	printDivisors(100); 
	return 0; 
}

• بايثون:

def printDivisors(n) : 
	i = 1
	while i <= n : 
		if (n % i==0) : 
			print i, 
		i = i + 1
		
# اختبار الدالة السابقة
print "The divisors of 100 are: "
printDivisors(100)

• جافا:

class Test 
{ 
	static void printDivisors(int n) 
	{ 
		for (int i=1;i<=n;i++) 
			if (n%i==0) 
				System.out.printf("%d ",i); 
	} 

	// اختبار التابع السابق
	public static void main(String args[]) 
	{ 
		System.out.println("The divisors of 100 are: "); 
		printDivisors(100);; 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

The divisors of 100 are: 
1 2 4 5 10 20 25 50 100

يبلغ التعقيد الزمني لهذه الطريقة المقدار O(n)‎.

الطريقة المحسنة

لو أمعنا النظر في قواسم عدد معين فسنجد أنّ جميع هذه القواسم موجودة على هيئة أزواج، فعلى سبيل المثال يمكن تمثيل قواسم العدد 100 بالأزواج التالية: ‎(1,100), (2,50), (4,25), (5,20), (10,10)‎.

يمكن الاستفادة من هذه الحقيقة في تحسين أداء الخوارزمية، ولكن يجب الانتباه إلى الحالات التي يكون فيها القاسمان متساويين مثل ‎(10, 10)‎، وفي مثل هذه الحالة يجب طباعة رقم واحد فقط.

• C++‎:

#include <bits/stdc++.h> 

void printDivisors(int n) 
{ 
	// تستمر هذه الحلقة في العمل إلى حين الوصول إلى الجذر التربيعي للعدد المعطى
	for (int i=1; i<=sqrt(n); i++) 
	{ 
		if (n%i == 0) 
		{ 
			// إن كان القاسمان متساويين نطبع أحدهما فقط
			if (n/i == i) 
				printf("%d ", i); 

			else // وإلا نطبعهما كلاهما
				printf("%d %d ", i, n/i); 
		} 
	} 
} 

/* اختبار الدالة السابقة */
int main() 
{ 
	printf("The divisors of 100 are: \n"); 
	printDivisors(100); 
	return 0; 
}

• بايثون:

import math 

def printDivisors(n) : 
	
	# تعمل هذه الحلقة التكرارية إلى حين الوصول إلى الجذر التربيعي للعدد المعطى
	i = 1
	while i <= math.sqrt(n): 
		
		if (n % i == 0) : 
			
			# إن كان القاسمان متساويين نطبع أحدهما 
			if (n / i == i) : 
				print i, 
			else : 
				# وإلا نطبعهما كلاهما
				print i , n/i, 
		i = i + 1

# اختبار الدالة السابقة 
print "The divisors of 100 are: "
printDivisors(100)

• جافا:

class Test 
{ 
	static void printDivisors(int n) 
	{ 
		// تعمل الحلقة التكرارية إلى حين الوصول إلى الجذر التربيعي للعدد المعطى
		for (int i=1; i<=Math.sqrt(n); i++) 
		{ 
			if (n%i==0) 
			{ 
				// إن كان القاسمان متساويين نطبع أحدهما
				if (n/i == i) 
					System.out.printf("%d ", i); 
	
				else // وإلا نطبعهما كلاهما
					System.out.printf("%d %d ", i, n/i); 
			} 
		} 
	} 

	// اختبار التابع السابق
	public static void main(String args[]) 
	{ 
		System.out.println("The divisors of 100 are: "); 
		printDivisors(100);; 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

The divisors of 100 are: 
1 100 2 50 4 25 5 20 10

يبلغ التعقيد الزمني لهذه الطريقة المقدار O(sqrt(n))‎.

طباعة مخرجات الخوارزمية مرتّبة

يمكن ملاحظة أنّ المخرجات التي حصلنا عليها في الطريقة السابقة تتبع نمطًا معيّنًا (الصغير، الكبير)، ولهذا إن جرى تخزين نصف العناصر فيمكن طباعة العناصر كلّها بالترتيب.

تعرض الأمثلة التالية طريقة طباعة قواسم عدد معيّن بالترتيب، وفي عدد من لغات البرمجة:

• C++:‎

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

void printDivisors(int n) 
{ 
	// يستخدم هذه المتّجه لتخزين نصف عدد القواسم
	vector<int> v; 
	for (int i=1; i<=sqrt(n); i++) 
	{ 
		if (n%i==0) 
		{ 
			if (n/i == i) // التحقق من كون القاسمين متساويين
				printf("%d ", i); 
			else
			{ 
				printf("%d ", i); 

				// إضافة القاسم الثاني إلى المتجّه
				v.push_back(n/i); 
			} 
		} 
	} 

	// طباعة المتّجه بالاتجاه العكسي
	for (int i=v.size()-1; i>=0; i--) 
		printf("%d ", v[i]); 
} 

/* اختبار الدالة السابقة */
int main() 
{ 
	printf("The divisors of 100 are: n"); 
	printDivisors(100); 
	return 0; 
}

• بايثون:

import math 

def printDivisors(n) : 
	list = [] 
	
	# قائمة لتخزين نصف عدد القواسم 
	for i in range(1, int(math.sqrt(n) + 1)) : 
		
		if (n % i == 0) : 
			
			# التحقق من كون القاسمين متساويين 
			if (n / i == i) : 
				print (i, end=" ") 
			else : 
				# وإلا طباعة القاسمين سوية 
				print (i, end=" ") 
				list.append(int(n / i)) 
				
	# طباعة عناصر القائمة بالاتجاه المعاكس
	for i in list[::-1] : 
		print (i, end=" ") 
		
# اختبار الدالة السابقة 
print ("The divisors of 100 are: ") 
printDivisors(100)

• جافا:

import java.util.Vector; 

class Test 
{ 
	static void printDivisors(int n) 
	{ 
		// يستخدم المتجه لتخزين نصف عدد القواسم
		Vector<Integer> v = new Vector<>(); 
		for (int i=1; i<=Math.sqrt(n); i++) 
		{ 
			if (n%i==0) 
			{ 
				if (n/i == i) // التحقق من كون القاسمين متساويين 
					System.out.printf("%d ", i); 
				else
				{ 
					System.out.printf("%d ", i); 
	
					// إضافة القاسم الثاني إلى المتّجه 
					v.add(n/i); 
				} 
			} 
		} 
	
		// طباعة عناصر المتجه بالاتجاه المعاكس
		for (int i=v.size()-1; i>=0; i--) 
			System.out.printf("%d ", v.get(i)); 
	} 

	// اختبار التابع السابق
	public static void main(String args[]) 
	{ 
		System.out.println("The divisors of 100 are: "); 
		printDivisors(100); 
	} 
}

مصادر

• صفحة Find all divisors of a natural number | Set 1 في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Find all divisors of a natural number | Set 2 في توثيق الخوارزميات في موقع GeeksforGeeks.