Algorithms/divisibility

يستخدم المعامل % في التحقق من قابلية قسمة عدد معين على عدد آخر وذلك بالحصول على النتيجة 0، ولكن عندما يصبح الرقم المعنيّ كبيرًا يصير من الصعب استخدام هذا المعامل للتحقق من قابلية القسمة، ولهذا نلجأ إلى بعض الخوارزميات التي تسهّل هذه العملية.

قابلية القسمة على 3

يكون العدد قابلًا للقسمة على 3 إذا كان مجموع أرقامه قابلًا للقسمة على 3.

فعلى سبيل المثال العدد n = 1332.

مجموع الأرقام = ‎1 + 3 + 3 + 2‎ = 9‎

ولمّا كان مجموع الأرقام قابلًا للقسمة على 3 فإنّ الرقم 1332 يقبل القسمة على 3.

يمكن برهنة ما سبق بكتابة العدد 1332 بالصيغة التالية:

1332 = 1*1000 + 3*1000 + 3*10 + 2

يستند البرهان على ما يلي:

باقي قسمة العدد ‎10^i‎ على 3 هو 1، وهذا يعني أنّ باقي قسمة أيّ قوّة للعدد 10 هو 1.

لذا يمكن كتابة باقي القسمة للمعادلة ‎1*1000 + 3*100 + 3*10 + 2‎ بالصيغة التالية:

1*1 + 3*1 + 3*1 + 2 = 9

يمثّل التعبير السابق مجموع الأرقام في العدد المعنيّ، ولمّا كان المجموع 9 قابلًا للقسمة على 3 فإنّ العدد 1332 يقبل القسم على 3.

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

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

• C++‎:

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

int check(string str) 
{ 
	// حساب مجموع الأرقام
	int n = str.length(); 
	int digitSum = 0; 
	for (int i=0; i<n; i++) 
		digitSum += (str[i]-'0'); 

	// التحقق من كون مجموع الأرقام قابلًا للقسمة على 3
	return (digitSum % 3 == 0); 
} 

// اختبار الشيفرة السابقة 
int main() 
{ 
	string str = "1332"; 
	check(str)? cout << "Yes" : cout << "No "; 
	return 0; 
}

• بايثون:

def check(num) : 
	
	# حساب مجموع الأرقام
	digitSum = 0
	while num > 0 : 
		rem = num % 10
		digitSum = digitSum + rem 
		num = num / 10
		
	# التحقق من كون مجموع الأرقام قابلًا للقسمة على 3
	return (digitSum % 3 == 0) 
	
# اختبار الشيفرة السابقة
num = 1332
if(check(num)) : 
	print "Yes"
else : 
	print "No"

• جافا:

class IsDivisible 
{ 
	static boolean check(String str) 
	{ 
		// حساب مجموع الأرقام
		int n = str.length(); 
		int digitSum = 0; 
		for (int i=0; i<n; i++) 
			digitSum += (str.charAt(i)-'0'); 
	
		// التحقق من كون مجموع الأرقام قابلًا للقسمة على 3 
		return (digitSum % 3 == 0); 
	} 

	// اختبار الشيفرة السابقة
	public static void main (String[] args) 
	{ 
		String str = "1332"; 
		if(check(str)) 
			System.out.println("Yes"); 
		else
			System.out.println("No"); 
	} 
}

قابلية القسمة على 4

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

يمتلك العدد 928160 على سبيل المثال الدورات: 928160 و 092816 و 609281 و 160928 و 816092 و 281609.

يمكن تشكيل الأزواج التالية من العدد الأصلي 928160:

(9,2) و (2,8) و (8,1) و (1,6) و (6,0) و (0,9).

يمكن ملاحظة أنّ الأعداد ثنائية الأرقام والتي تنشأ من هذه الأزواج (أي 92 و 28 و 81 و 16 و 60، و 09) موجود في نهاية بعض الدورات؛ وبهذا يمكن التحقق من قابلية قسمة هذه الأزواج للحول على عدد الدورات المطلوبة للعدد.

ملاحظة:: يمكن التحقق من قابلية القسمة للأعداد المفردة بطريقة مباشرة.

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

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

• C++‎:

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

// تحسب هذه الدالة جميع التدويرات التي تقبل القسمة على 4
int countRotations(string n) 
{ 
	int len = n.length(); 

	// لعدد أحادي المرتبة
	if (len == 1) 
	{ 
		int oneDigit = n.at(0)-'0'; 
		if (oneDigit%4 == 0) 
			return 1; 
		return 0; 
	}

	// عدد ثنائي المراتب على الأقل (مع الأخذ بجميع الأزواج)  
	int twoDigit, count = 0; 
	for (int i=0; i<(len-1); i++)
	{
		twoDigit = (n.at(i)-'0')*10 + (n.at(i+1)-'0'); 
		if (twoDigit%4 == 0) 
			count++; 
	} 

	// العدد الذي يتكون من الرقمين الأخير والأول
	twoDigit = (n.at(len-1)-'0')*10 + (n.at(0)-'0'); 
	if (twoDigit%4 == 0) 
		count++; 

	return count; 
} 

// اختبار الشيفرة السابقة
int main() 
{ 
	string n = "4834"; 
	cout << "Rotations: " << countRotations(n) << endl; 
	return 0; 
}

• بايثون:

#تحسب هذه الدالة جميع التدويرات التي تقبل القسمة على 4 
def countRotations(n) : 

	l = len(n) 

	# لعدد أحادي المرتبة 
	if (l == 1) : 
		oneDigit = (int)(n[0]) 
		
		if (oneDigit % 4 == 0) : 
			return 1
		return 0
	
	
	# عدد ثنائي المراتب على الأقل (مع الأخذ بجميع الأزواج)
	count = 0
	for i in range(0, l - 1) : 
		twoDigit = (int)(n[i]) * 10 + (int)(n[i + 1]) 
		
		if (twoDigit % 4 == 0) : 
			count = count + 1
			
	# العدد الذي يتكون من الرقمين الأخير والأول 
	twoDigit = (int)(n[l - 1]) * 10 + (int)(n[0]) 
	if (twoDigit % 4 == 0) : 
		count = count + 1

	return count 

# اختبار الشيفرة السابقة
n = "4834"
print("Rotations: " , 
	countRotations(n))

• جافا:

import java.io.*; 

class GFG { 
	
	// تحسب هذه الدالة جميع التدويرات التي تقبل القسمة على 4 
	static int countRotations(String n) 
	{ 
		int len = n.length(); 
	
		// لعدد أحادي المرتبة 
		if (len == 1) 
		{ 
		int oneDigit = n.charAt(0)-'0'; 

		if (oneDigit % 4 == 0) 
			return 1; 

		return 0; 
		} 
	
		// عدد ثنائي المراتب على الأقل (مع الأخذ بجميع الأزواج)
		int twoDigit, count = 0; 
		for (int i = 0; i < (len-1); i++) 
		{ 
		twoDigit = (n.charAt(i)-'0') * 10 + 
					(n.charAt(i+1)-'0'); 

		if (twoDigit%4 == 0) 
			count++; 
		} 
	
		// العدد الذي يتكون من الرقمين الأخير والأول  
		twoDigit = (n.charAt(len-1)-'0') * 10 + 
				(n.charAt(0)-'0'); 

		if (twoDigit%4 == 0) 
			count++; 
	
		return count; 
	} 
	
	// اختبار الشيفرة السابقة
	public static void main(String args[]) 
	{ 
		String n = "4834"; 
		System.out.println("Rotations: " + 
						countRotations(n)); 
	} 
}

قابلية القسمة على 5

يكون العدد قابلاً للقسمة على 5 إذا كان آخر رقم فيه هو 0 أو 5.

يمكن برهنة ما سبق بواسطة الملاحظة التالية:

إن باقي قسمة ‎10^i‎ على 5 يساوي 0 إذا كانت i >= 1. يلاحظ أنّ باقي قسمة الأعداد 10 و 100 و 1000 و... الخ على 5 هو 0.

ولهذا فإنّ باقي قسمة ‎"5*1000 + 3*100 + 3*10 + 5"‎ على 5 مكافئ لباقي قسمة: ‎0 + 0 + 0 + 5 = 5‎، ولما كانت 5 تقبل القسمة على 5 فإن العدد 5335 يقبل القسمة على 5.

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

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

• C++‎:

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

// تتحقق الدالة من كون العدد المعطى قابلاً للقسمة على 5
// تفترض الدالة أنّ طول السلسلة النصية هو 1 على الأقل
bool isDivisibleBy5(string str) 
{ 
	int n = str.length(); 

	return ( ((str[n-1]-'0') == 0) || 
			((str[n-1]-'0') == 5)); 
} 

// اختبار الشيفرة السابقة
int main() 
{ 
	string str = "76955"; 
	isDivisibleBy5(str)? cout << "Yes" : 
						cout << "No "; 
	return 0; 
}

• بايثون:

# تتحقق الدالة من كون العدد المعطى قابلاً للقسمة على 5
# تفترض الدالة أنّ طول السلسلة النصية هو 1 على الأقل 
def isDivisibleBy5(st) : 
	return ((st[-1] == '0') or (st[-1] == '5'))

# اختبار الشيفرة السابقة
st = "76955"
if isDivisibleBy5(st) : 
	print("Yes")
else : 
	print("No")

• جافا:

class IsDivisible 
{ 
	// يتحقق التابع من كون العدد المعطى قابلاً للقسمة على 5
	// يفترض التابع أنّ طول السلسلة النصية هو 1 على الأقل 
	static boolean isDivisibleBy5(String str) 
	{ 
		int n = str.length(); 
	
		return ( ((str.charAt(n-1)-'0') == 0) || 
				((str.charAt(n-1)-'0') == 5)); 
	} 
	
	// اختبار الشيفرة السابقة
	public static void main (String[] args) 
	{ 
		String str = "76955"; 
		if(isDivisibleBy5(str)) 
			System.out.println("Yes"); 
		else
			System.out.println("No"); 
	} 
}

قابلية القسمة على 6

يقبل العدد القسمة على 6 إذا كان يقبل القسمة على 2 و 3، وهذا يعني أنّه يجب أن يحقق الشرطين التاليين:

1. يقبل العدد القسمة على 2 إذا كان آخر رقم فيه قابلًا للقسمة على 2.
2. يقبل العدد القسمة على 3 إذا كان مجموع أرقامه قابلاً للقسمة على 3.

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

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

• C++‎:

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

// تتحقق الدالة من قابلية قسمة العدد المعطى -كسلسلة نصية- على 6
bool check(string str) 
{ 
	int n = str.length(); 

	// يعيد هذا الشرط قيمة خاطئة إن لم يكن العدد قابلًا للقسمة على 2
	if ((str[n-1]-'0')%2 != 0) 
	return false; 

	// الوصول إلى هنا يعني أنّ العدد قابل للقسمة على 2
	// التحقق من قابلية القسمة على 3

	// حساب مجموع الأرقام
	int digitSum = 0; 
	for (int i=0; i<n; i++) 
		digitSum += (str[i]-'0'); 

	// التحقق من أن مجموع الأرقام قابل للقسمة على 3
	return (digitSum % 3 == 0); 
} 

// اختبار الدالة السابقة
int main() 
{ 
	string str = "1332"; 
	check(str)? cout << "Yes" : cout << "No "; 
	return 0; 
}

• بايثون:

# تتحقق الدالة من قابلية قسمة العدد المعطى -كسلسلة نصية- على 6 
def check(st) : 
	n = len(st) 
	
	
	# يعيد هذا الشرط قيمة خاطئة إن لم يكن العدد قابلًا للقسمة على 2
	if (((int)(st[n-1])%2) != 0) : 
		return False

	# الوصول إلى هنا يعني أنّ العدد قابل للقسمة على 2
	# التحقق من قابلية القسمة على 3

	# حساب مجموع الأرقام
	digitSum = 0
	for i in range(0, n) : 
		digitSum = digitSum + (int)(st[i]) 

	# التحقق من أن مجموع الأرقام قابل للقسمة على 3
	return (digitSum % 3 == 0) 


# اختبار الشيفرة السابقة 
st = "1332"
if(check(st)) : 
	print("Yes") 
else : 
	print("No ")

• جافا:

class IsDivisible 
{ 
	// تتحقق الدالة من قابلية قسمة العدد المعطى -كسلسلة نصية- على 6
	static boolean check(String str) 
	{ 
		int n = str.length(); 
	
		//  يعيد هذا الشرط قيمة خاطئة إن لم يكن العدد قابلًا للقسمة على 2 
		if ((str.charAt(n-1) -'0')%2 != 0) 
		return false; 
	
		// الوصول إلى هنا يعني أنّ العدد قابل للقسمة على 2
		// التحقق من قابلية القسمة على 3
		
		// حساب مجموع الأرقام
		int digitSum = 0; 
		for (int i=0; i<n; i++) 
			digitSum += (str.charAt(i)-'0'); 
	
		// التحقق من أن مجموع الأرقام قابل للقسمة على 3
		return (digitSum % 3 == 0); 
	} 
	
	// اختبار الدالة السابقة
	public static void main (String[] args) 
	{ 
		String str = "1332"; 
		if(check(str)) 
			System.out.println("Yes"); 
		else
			System.out.println("No"); 
	} 
}

قابلية القسمة على 7

يمكن التحقق من قابلية قسمة عدد معين على 7 باستخدام طريقة تعاودية، وتعتمد هذه الطريقة على أنّ العدد الذي يكون بالصيغة 10a + b قابلًا للقسمة على 7 إذا وفقط إذا كانت ناتج العملية a - 2b قابلاً للقسمة على 7. وبمعنى آخر، نطرح ضعف الرقم الأخير من الرقم الناتج من بقية الأرقام، ونستمر في ذلك إلى حين الحصول على رقم يقبل القسمة على 7.

فمثلًا: العدد 371:

37 – (2 × 1) = 37 – 2 = 35
3 – (2 × 5) = 3 – 10 = –7

لمّا كان العدد 7– يقبل القسمة على 7 فإنّ العدد 371 يقبل القسمة على 7.

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

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

• C++‎:

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

int isDivisibleBy7( int num ) 
{ 
	// نحول العدد السالب إلى موجب
	if( num < 0 ) 
		return isDivisibleBy7( -num ); 

	// الحالات الأساسية
	if( num == 0 || num == 7 ) 
		return 1; 
	if( num < 10 ) 
		return 0; 

	// تستدعي الدالة نفسها 
	return isDivisibleBy7( num / 10 - 2 * 
			( num - num / 10 * 10 ) ); 
} 

// اختبار الشيفرة السابقة
int main() 
{ 
	int num = 616; 
	if( isDivisibleBy7(num ) ) 
		cout << "Divisible" ; 
	else
		cout << "Not Divisible" ; 
	return 0; 
}

• بايثون:

def isDivisibleBy7(num) : 
	
	#  نحول العدد السالب إلى موجب
	if num < 0 : 
		return isDivisibleBy7( -num ) 

	# الحالات الأساسية
	if( num == 0 or num == 7 ) : 
		return True
	
	if( num < 10 ) : 
		return False
		
	# تستدعي الدالة نفسها
	return isDivisibleBy7( num / 10 - 2 * ( num - num / 10 * 10 ) ) 
	
# اختبار الشيفرة السابقة
num = 616
if(isDivisibleBy7(num)) : 
	print "Divisible"
else : 
	print "Not Divisible"

• جافا:

import java.io.*; 

class GFG 
{ 
	static boolean isDivisibleBy7(int num) 
	{ 
		// تحويل العدد السالب إلى موجب
		if( num < 0 ) 
			return isDivisibleBy7( -num ); 

		// الحالات الأساسية
		if( num == 0 || num == 7 ) 
			return true; 
		if( num < 10 ) 
			return false; 

		// تستدعي الدالة نفسها
		return isDivisibleBy7( num / 10 - 2 * ( num - num / 10 * 10 ) ); 
	} 
	
	// اختبار الشيفرة السابقة
	public static void main (String[] args) 
	{ 
		int num = 616; 
		if(isDivisibleBy7(num)) 
			System.out.println("Divisible"); 
		else
			System.out.println("Not Divisible"); 
	} 
}

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

Divisible

قابلية القسمة على 8

يقبل العدد القسمة على 8 إن كان العدد المتشكِّل من الأرقام الثلاثة الأخيرة فيه قابلًا للقسمة على 8.

مثال: الرقم 76952.

العدد المتشكِّل من الأرقام الثلاثة الأخيرة هو 952، ولمّا كان هذا العدد قابلًا للقسمة على 8 فإنّ العدد 76952 يقبل القسمة على 8.

يمكن كتابة العدد 76942 بالصيغة:

76942 = 7*10000 + 6*1000 + 9*100 + 5*10 + 2

يمكن إثبات ذلك بالاستفادة من الملاحظة التالية:

يكون باقي قسمة العدد ‎10^i‎ على 8 مساويًا للصفر إن كانت i >= 3. أي أنّ باقي قسمة الأعداد 1000 و 10000 و... الخ على 8 هو 0.

ولهذا فإنّ باقي قسمة المقدار ‎"7*10000 + 6*1000 + 9*100 + 5*10 + 2"‎ على 8 يكون مكافئًا لباقي المقدار ‎‎0 + 0 + 9*100 + 5*10 + 2 = 952‎.

وهكذا يمكن القول أنّ العدد الأصلي قابل للقسمة على 8 إن كانت 952 تقبل القسمة على 8.

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

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

• C++‎:

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

bool check(string str) 
{ 
	int n = str.length(); 

	// سلسلة نصية فارغة
	if (n == 0) 
		return false; 

	// إن كان العدد أحادي المرتبة
	if (n == 1) 
		return ((str[0]-'0')%8 == 0); 

	// إن كان العدد ثنائي المرتبة
	if (n == 2) 
		return (((str[n-2]-'0')*10 + (str[n-1]-'0'))%8 == 0); 

	// إن كان العدد المكوّن من الأرقام الثلاثة الأخيرة يقبل القسمة على 8
	int last = str[n-1] - '0'; 
	int second_last = str[n-2] - '0'; 
	int third_last = str[n-3] - '0'; 

	return ((third_last*100 + second_last*10 + last) % 8 == 0); 
} 

// اختبار الشيفرة السابقة
int main() 
{ 
	string str = "76952"; 
	check(str)? cout << "Yes" : cout << "No "; 
	return 0; 
}

• بايثون:

def check(st) : 
	n = len(st) 
	
	# سلسلة نصية فارغة
	if (n == 0) : 
		return False

	# إن كان العدد أحادي المرتبة
	if (n == 1) : 
		return ((int)(st[0]) % 8 == 0) 

	# إن كان العدد ثنائي المرتبة
	if (n == 2) : 
		return ((int)(st[n - 2]) * 10 +
		((int)(str[n - 1]) % 8 == 0)) 

	# إن كان العدد المكوّن من الأرقام الثلاثة الأخيرة يقبل القسمة على 8 
	last = (int)(st[n - 1]) 
	second_last = (int)(st[n - 2]) 
	third_last = (int)(st[n - 3]) 

	return ((third_last*100 + second_last*10 +
							last) % 8 == 0) 


# اختبار الشيفرة السابقة
st = "76952"

if(check(st)) : 
	print("Yes") 
else : 
	print("No ")

• جافا:

class IsDivisible 
{ 
	static boolean check(String str) 
	{ 
		int n = str.length(); 
	
		// سلسلة نصية فارغة 
		if (n == 0) 
			return false; 
	
		// إن كان العدد أحادي المرتبة
		if (n == 1) 
			return ((str.charAt(0)-'0')%8 == 0); 
	
		// إن كان العدد ثنائي المرتبة
		if (n == 2) 
			return (((str.charAt(n-2)-'0')*10 + (str.charAt(n-1)-'0'))%8 == 0); 
	
		// إن كان العدد المكوّن من الأرقام الثلاثة الأخيرة يقبل القسمة على 8 
		int last = str.charAt(n-1) - '0'; 
		int second_last = str.charAt(n-2) - '0'; 
		int third_last = str.charAt(n-3) - '0'; 
	
		return ((third_last*100 + second_last*10 + last) % 8 == 0); 
	} 
	
	// اختبار الشيفرة السابقة
	public static void main (String[] args) 
	{ 
		String str = "76952"; 
		if(check(str)) 
			System.out.println("Yes"); 
		else
			System.out.println("No"); 
	} 
}

قابلية القسمة على 9

يكون العدد قابلًا للقسمة على 9 إذا كان مجموع أرقامه قابلًا للقسمة على 9.

تتبع هذه الخوارزمية نفس الخطوات التي تتبعها خوارزمية قابلية القسمة على 3، باستثناء أنّ الخطوة الأخيرة تتحقق من قابلية قسمة حاصل جمع الأرقام على 9 عوضًا عن 3.

مصادر

• صفحة Check if a large number is divisible by 3 or not في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Check if a large number is divisible by 4 or not في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Check if a large number is divisible by 6 or not في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Check divisibility by 7 في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Count rotations divisible by 8 في توثيق الخوارزميات في موقع GeeksforGeeks.