Algorithms/prime numbers

العدد الأولي هو عدد يكون أكبر من 1 ويقبل القسمة على 1 وعلى نفسه فقط.

هناك عدة طرق للتحقق من كون العدد المعطى عددًا أوّليًّا أو لا.

الخوارزمية البسيطة

إن أبسط طريقة للكشف عن كون عدد معيّن (ليكن n) عددًا أوليًا هي في المرور على جميع الأرقام ضمن النطاق 2 و n-1، ونتحقق عند كل عدد ممّا إذا كان ذلك العدد يقسم n دون باقٍ، فإذا وجد مثل هذا الرقم تعيد الدالة قيمة خاطئة ويكون العدد عددًا غير أولي.

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

• C++‎:

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

bool isPrime(int n) 
{ 
	// إن كان العدد المعطى أقل من 1 أو يساويه تعيد الدالة قيمة خاطئة
	if (n <= 1) 
		return false; 

	// n - 1 التحقق ضمن النطاق 2 و
	for (int i = 2; i < n; i++) 
		if (n % i == 0) 
			return false; 

	return true; 
} 

// اختبار الدالة السابقة
int main() 
{ 
	isPrime(11) ? cout << " true\n" : 
				cout << " false\n"; 
	return 0; 
}

• بايثون:

def isPrime(n): 
	
	# إن كان العدد المعطى أقل من 1 أو يساويه تعيد الدالة قيمة خاطئة
	if (n <= 1): 
		return False

	# n - 1 التحقق ضمن النطاق 2 و 
	for i in range(2, n): 
		if (n % i == 0): 
			return False

	return True

# اختبار الدالة السابقة 
if isPrime(11): 
	print ("true") 
else: 
	print ("false")

• جافا:

import java.util.*; 

class GFG { 
	
	static boolean isPrime(int n) 
	{ 
		// إن كان العدد المعطى أقل من 1 أو يساويه تعيد الدالة قيمة خاطئة
		if (n <= 1) 
			return false; 
	
		// إن كان العدد المعطى أقل من 1 أو يساويه تعيد الدالة قيمة خاطئة 
		for (int i = 2; i < n; i++) 
			if (n % i == 0) 
				return false; 
	
		return true; 
	} 
	
	/* اختبار الدالة السابقة */
	public static void main(String[] args) 
	{ 
		if(isPrime(11)) 
		System.out.println(" true") ; 
		
		else
		System.out.println(" false"); 
		
	} 
}

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

true
false

التعقيد الزمني

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

تحسين الخوارزمية البسيطة

يمكن إجراء التحسينات التالية على الخوارزمية البسيطة:

• يمكن التحقق من كون العدد المعطى عددًا أوليًّا ضمن النطاق 2 و ‎√n‎ عوضًا عن n؛ وذلك لأنّ العامل الأكبر للعدد n يجب أن يكون مضاعفًا للعامل الأصغر الذي جرى التحقق منه فعلًا.
• يمكن تحسين الخوارزمية البسيطة بالاعتماد على القاعدة التي تنصّ على أنّ بالإمكان التعبير عن جميع الأعداد الأولية بالصيغة الرياضية 6k ± 1 باستثناء العددين الأوليين 2 و 3؛ وذلك لأنّ بالإمكا نالتعبير عن جميع الأعداد الصحيحة بالصيغة (6k + i) لبعض الأعداد الصحيحة k ولقيم i التي تساوي ‎‎-1‎ أو 0 أو 1 أو 2 أو 3 أو 4. إذ يقسم العدد 2 الأعداد (6k + 0) و (6k + 2) و (6k + 4)، ويقسم العدد 3 العدد (6k + 3). ولهذا فإنّ الطريقة الأكثر فعالية هي التحقق من أنّ العدد المعطى n يقبل القسمة على 2 أو 3، ثم التحقق من جميع الأرقام التي يمكن التعبير عنها بالصيغة 6k ± 1.

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

• C++‎:

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

bool isPrime(int n) 
{ 
	if (n <= 1) return false; 
	if (n <= 3) return true; 

	// تم التحقق من هذا لذا يمكن تجاوز الأعداد الخمسة الوسطى
	// في الحلقة التكرارية أدناه
	if (n%2 == 0 || n%3 == 0) return false; 

	for (int i=5; i*i<=n; i=i+6) 
		if (n%i == 0 || n%(i+2) == 0) 
		return false; 

	return true; 
} 


// اختبار الدالة السابقة
int main() 
{ 
	isPrime(11)? cout << " true\n": cout << " false\n"; 
	isPrime(15)? cout << " true\n": cout << " false\n"; 
	return 0; 
}

• بايثون:

def isPrime(n) : 
	if (n <= 1) : 
		return False
	if (n <= 3) : 
		return True

		# تم التحقق من هذا لذا يمكن تجاوز الأعداد الخمسة الوسطى
		# في الحلقة التكرارية أدناه 
	if (n % 2 == 0 or n % 3 == 0) : 
		return False

	i = 5
	while(i * i <= n) : 
		if (n % i == 0 or n % (i + 2) == 0) : 
			return False
		i = i + 6

	return True


# اختبار الدالة السابقة

if(isPrime(11)) : 
	print(" true") 
else : 
	print(" false") 
	
if(isPrime(15)) : 
	print(" true") 
else : 
	print(" false")

• جافا:

import java.io.*; 

class GFG { 
	
	static boolean isPrime(int n) 
	{ 
		if (n <= 1) return false; 
		if (n <= 3) return true; 
	
		// تم التحقق من هذا لذا يمكن تجاوز الأعداد الخمسة الوسطى
		// في الحلقة التكرارية أدناه 
		if (n % 2 == 0 || n % 3 == 0) return false; 
	
		for (int i = 5; i * i <= n; i = i + 6) 
			if (n % i == 0 || n % (i + 2) == 0) 
			return false; 
	
		return true; 
	} 


	// اختبار التابع السابق
	public static void main(String args[]) 
	{ 
		if(isPrime(11)) 
			System.out.println(" true"); 
		else
			System.out.println(" false"); 
		if(isPrime(15)) 
			System.out.println(" true"); 
		else
			System.out.println(" false"); 
		
	} 
}

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

true
false

التعقيد الزمني

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

طريقة فيرمات

طريقة فيرمات Fermat Method طريقة احتمالية probabilistic وتعتمد على مبرهنة فيرمات الصغيرة، والتي تنصّ على أنّه إن كان n عددًا أوليًّا، فلكل a إذ ‎1 < a < n-1‎ فإنّ:

a^(n-1) ≡ 1 (mod n)

أو

a^(n-1) % n = 1

مثال:

العدد 5 عدد أولي:

2^4 ≡ 1 (mod 5) [2^4%5 = 1],
3^4 ≡ 1 (mod 5) and 4^4 ≡ 1 (mod 5) 

العدد 7 عدد أولي:
2^6 ≡ 1 (mod 7),
3^6 ≡ 1 (mod 7), 4^6 ≡ 1 (mod 7) 
5^6 ≡ 1 (mod 7) and 6^6 ≡ 1 (mod 7)

إن كان العدد المعطى أوليًا فإن هذه الطريقة تعيد قيمة صحيحة دائمًا، ولكن إن كان العدد المعطى مركًّبا composite أو غير أولي، فقد تعيد الطريقة قيمة صحيحة أو خاطئة، ولكن احتمالية إعطاء نتيجة خاطئة مع الأعداد المركبة صغيرة ويمكن تقليلها بإجراء المزيد من عمليات التكرار.

تشير قيمة k المرتفعة إلى زيادة في احتمالية الحصول على نتيجة صحيحة مع الأرقام المركبة، ولكن الأعداد الأولية تعطي نتيجة صحيحة دائمًا.

يمكن تقسيم الخوارزمية إلى الخطوات التالية:

1. تكرار الخطوات التالية k مرة:
   

أ) اختيار a عشوائيًا من النطاق ‎[2, n-2]‎.
ب) إن كان القاسم المشترك الأكبر للعددين لا يساوي واحد gcd(a, n) ≠ 1، نعيد قيمة خاطئة
جـ) إن تحققت العلاقة ‎an-1 ≢ 1 (mod n)‎، نعيد قيمة خاطئة

1. نعيد قيمة صحيحة (من المحتمل أن العدد المعطى عدد أوليّ).

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

• C++‎:

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

/* دالة تكرارية تستخدم لحساب
(a^n)%p
 O(logy)‎ بتعقيد زمني قدره */
int power(int a, unsigned int n, int p) 
{ 
	int res = 1;	 // تهيئة النتيجة
	a = a % p; // a تحديث قيمة

	while (n > 0) 
	{ 
		// a إن كان العدد المعطى فرديًا نضرب النتيجة بالعدد
		if (n & 1) 
			res = (res*a) % p; 
	
		// يجب أن يتحول العدد المعطى إلى عدد زوجي عند هذه النقطة
		n = n>>1; // n = n/2 
		a = (a*a) % p; 
	} 
	return res; 
} 

/* دالة تعاودية لحساب القاسم المشترك الأكبر لعددين */
int gcd(int a, int b) 
{ 
	if(a < b) 
		return gcd(b, a); 
	else if(a%b == 0) 
		return b; 
	else return gcd(b, a%b); 
} 

// إن كان العدد المعطى أوليًا، فإنّ الدالة تعيد قيمة صحيحة دائمًا
// أما إن كان العدد المعطى مركبًا، فإن الدالة تعيد قيمة خاطئة مع احتمالية عالية
// k تؤدي زيادة قيمة
// إلى زيادة احتمالية الحصول على نتيجة صحيحة
bool isPrime(unsigned int n, int k) 
{ 
if (n <= 1 || n == 4) return false; 
if (n <= 3) return true; 

// تنفيذ الحلقة التكرارية
while (k>0) 
{ 
	//  [2..n-2] اختيار رقم عشوائي من النطاق
	// تضمن العبارات الشرطية أعلاه أنّ قيمة العدد المعطى أكبر من 4
	int a = 2 + rand()%(n-4); 

	// التحقق من أنّ العددين أوليين فيما بينهما
	if (gcd(n, a) != 1) 
		return false; 
	
	// مبرهنة فيرمات الصغيرة
	if (power(a, n-1, n) != 1) 
		return false; 
	
	k--; 
	} 
	
	return true; 
} 

// اختبار الدوال السابقة 
int main() 
{ 
	int k = 3; 
	isPrime(11, k)? cout << " true\n": cout << " false\n"; 
	isPrime(15, k)? cout << " true\n": cout << " false\n"; 
	return 0; 
}

• بايثون:

import random
def power(a, n, p):
    res = 1  # تهيئة النتيجة
    a = a % p # a تحديث قيمة

    while (n > 0):
		# a إن كان العدد المعطى فرديًا نضرب النتيجة بالعدد
        if (n & 1):
            res = (res*a) % p
		# يجب أن يتحول العدد المعطى إلى عدد زوجي عند هذه النقطة
        n = n >> 1
        a = (a * a) % p
    
    return res

# إن كان العدد المعطى أوليًا، فإنّ الدالة تعيد قيمة صحيحة دائمًا
# أما إن كان العدد المعطى مركبًا، فإن الدالة تعيد قيمة خاطئة مع احتمالية عالية
# k تؤدي زيادة قيمة
# إلى زيادة احتمالية الحصول على نتيجة صحيحة
def isPrime(n, k):
    if (n <= 1 or n == 4):
        return False
    if (n <= 3):
        return True
	# تنفيذ الحلقة التكرارية
    while (k > 0):
        #  [2..n-2] اختيار رقم عشوائي من النطاق
		# تضمن العبارات الشرطية أعلاه أنّ قيمة العدد المعطى أكبر من 4
        a = 2 + random.randint(2,n - 2) % (n - 4)
		
        # مبرهنة فيرمات الصغيرة
		if (power(a, n-1, n) != 1):
            return False
        
        k-=1

    return True

# اختبار الدوال السابقة
k = 3
res = isPrime(11, k) if " true\n" else "false\n"
print(res)

res = isPrime(15, k) if " true\n" else "false\n"
print(res)

• جافا:

import java.io.*; 
import java.math.*; 

class GFG { 
	
	/* دالة تكرارية تستخدم لحساب
	(a^n)%p
 	O(logy)‎ بتعقيد زمني قدره */
	static int power(int a,int n, int p) 
	{ 
		// تهيئة النتيجة 
		int res = 1; 
		
		// a تحديث قيمة 
		a = a % p; 
	
		while (n > 0) 
		{ 
			// a إن كان العدد المعطى فرديًا نضرب النتيجة بالعدد 
			if ((n & 1) == 1) 
				res = (res * a) % p; 
	
			//  يجب أن يتحول العدد المعطى إلى عدد زوجي عند هذه النقطة 
			n = n >> 1; // n = n/2 
			a = (a * a) % p; 
		} 
		return res; 
	} 
	
	// إن كان العدد المعطى أوليًا، فإنّ الدالة تعيد قيمة صحيحة دائمًا
	// أما إن كان العدد المعطى مركبًا، فإن الدالة تعيد قيمة خاطئة مع احتمالية عالية
	// k تؤدي زيادة قيمة
	// إلى زيادة احتمالية الحصول على نتيجة صحيحة
	static boolean isPrime(int n, int k) 
	{ 
	if (n <= 1 || n == 4) return false; 
	if (n <= 3) return true; 
	
	// تنفيذ الحلقة التكرارية 
	while (k > 0) 
	{ 
		//  [2..n-2] اختيار رقم عشوائي من النطاق
		//  تضمن العبارات الشرطية أعلاه أنّ قيمة العدد المعطى أكبر من 4 
		int a = 2 + (int)(Math.random() % (n - 4)); 
	
		// مبرهنة فيرمات الصغيرة 
		if (power(a, n - 1, n) != 1) 
			return false; 
	
		k--; 
		} 
	
		return true; 
	} 
	
	// اختبار الدوال السابقة 
	public static void main(String args[]) 
	{ 
		int k = 3; 
		if(isPrime(11, k)) 
			System.out.println(" true"); 
		else
			System.out.println(" false"); 
		if(isPrime(15, k)) 
			System.out.println(" true"); 
		else
			System.out.println(" false"); 
			
	} 
}

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

true
false

التعقيد الزمني

يبلغ التعقيد الزمني لطريقة فيرمات المقدار O(k Log n)‎، مع ملاحظة أنّ التعقيد الزمني لدالة القوة يبلغ O(Log n)‎

ملاحظة:

قد تعطي هذه الطريقة نتائجة خاطئة حتى عند زيادة عدد الدورات (قيمة k أعلى)، إذ توجد بعض الأعداد المركبة والتي تمتلك الخاصية التالية لكل a < n وهي أنّ القاسم المشترك الأكبر للعددين a و n يساوي 1، وأنّ ‎a^(n-1) ≡ 1 (mod n)‎. تسمى هذه الأعداد بأعداد كارمايكل Carmichael.

يستخدم اختبار فيرمات لأولية الأعداد غالبًا عند الحاجة إلى طريقة سريعة لتصفية الأعداد، فمثلًا تستخدم هذه الطريقة في طور إنشاء المفتاح في خوارزمية مفتاح RSA العمومي للتشفير.

طريقة ميلر-رابين

طريقة ميلر-رابين Miller-Rabin هي طريقة اعتمادية مثل طريقة فيرمات، ولكنّها مفضّلة عليها عمومًا.

1. تنصّ مبرهنة فيرمات على أنّه إن كان العدد n عددًا أوليًّا فلكل a إذ ‎1 < a < n-1‎ فإنّ: ‎a^n-1 % n = 1‎.
2. تضمن الحالات الأساسية أن يكون العدد المعطى n عددًا فرديًا، ولما كان n فرديًا فإنّ n-1 سيكون زوجيًا حتمًا، ويمكن كتابة الأرقام الزوجية بالصيغة d * 2s إذ d عدد فردي و s > 0.
3. تحتم النقطتان أعلاه أن يكون حاصل العملية a^d*2r % 2 هو 1 لكل رقم عشوائي في النطاق ‎[2, n-2]‎.
4. حسب موضوعة إقليدس Euclid’s Lemma فإن كان x^2 % n = 1 أو ‎(x2 – 1) % n = 0 ولكي يكون n عددًا أوليًّا، يجب أن يقسم المقدار (x-1) أو المقدار (x+1)،وهذا يعني تحقق العلاقة x % n = 1 أو x % n = -1.
5. يمكن استنتاج ما يلي بالاستعانة بالنقطتين 2 و 3:

ليكون العدد n عددًا أوليًا يجب تحقق أحد الشرطين التاليين:
a^d % n = 1
أو:
a^d*2i % n = -1
لبعض قيم i عندما تكون ‎0 <= i <= r-1‎

خطوات الخوارزمية

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

تضمّ هذه الخوارزمية دالتين هما:

1. bool isPrime(int n, int k)‎

تعطي هذه الدالة نتيجة منطقية، وتؤدي العمليات التالية:

1. تعالج الحالة الأساسية والتي يكون فيها العدد المعطى أقل من 3.

2. إن كان العدد المعطى موجبًا، تعيد الدالة قيمة خاطئة.

3. العثور على عد فردي d يمكن استخدامه لكتابة العدد n-1 بالصيغة d*2r. لاحظ أنّه لما كان العدد n فرديًا فإنّ العدد n-1 سيكون زوجيًا ويجب أن تكون قيمة r أكبر من الصفر.

4. تؤدي الدالة العملية التالية k مرة:

   if (millerTest(n, d) == false)‎
return false

5. إعادة قيمة صحيحة.

1. bool millerTest(int n, int d)‎

تستدعى هذه الدالة k مرة، وتعيد قيمة خاطئة إن كان العدد n عددًا مركّبًا، وتعيد قيمة خاطئة إن كان هناك احتمال في أن يكون العدد n عددًا أوليًّا. العدد d هو عدد فردي يحقق العلاقة d*2r = n-1 لبعض قيم r التي تكون أكبر من واحد أو مساوية له.

تعطي هذه الدالة نتيجة منطقية، وتؤدي العمليات التالية:

1. اختيار رقم عشوائي a من النطاق ‎[2, n-2]‎.

2. حساب نتيجة العملية: x = pow(a, d) % n

3. إن كانت x == 1 أو x == n-1، تعيد الدالة قيمة صحيحة.

4. تنفيذ الحلقة التكرارية (تنفّذ r-1 مرة في الغالب) بشرط أن لا تصبح قيمة d مساوية للعدد n-1:

   a) x = (x*x) % n‎
b) If (x == 1) return false‎
c) If (x == n-1) return true

يوضّح المثال التالي طريقة سير عمل الخوارزمية:

المدخلات: n = 13, k = 2.

1) حساب قيمة d و r بشرط تحقيق العلاقة d*2r = n-1

d = 3, r = 2. 

2) استدعاء الدالة millerTest وتكرار الاستدعاء k مرة.

الدورة الأولى:

1) اختيار رقم عشوائي a من النطاق ‎[2, n-2]‎. لنفترض أن a = 4.

2) حساب نتيجة المعادلة x = pow(a, d)‎ % n

x = 43 % 13 = 12

3) لما كان x = (n-1)‎، تعيد الدالة قيمة صحيحة.

الدورة الثانية:

1) اختيار رقم عشوائي a من النطاق ‎[2, n-2]‎. لنفترض أن a = 5.

2) حساب نتيجة المعادلة x = pow(a, d) % n.

x = 53 % 13 = 8

3) x لا تساوي 1 أو 12.

4) تنفيذ ما يلي (r-1) مرة = مرة واحدة.

a) x = (x * x) % 13 = (8 * 8) % 13 = 12

b) لما كان ‎x = (n-1)‎ تعيد الدالة قيمة صحيحة.

لما كانت الدورتان تعيدان قيمة صحيحة، فسنعيد قيمة صحيحة.

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

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

• C++‎:

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

// دالة مساعدة لرفع الرقم المعطى إلى قوة معينة ثم حساب باقي القسمة على عدد ثالث

//(x^y) % p 
int power(int x, unsigned int y, int p) 
{ 
	int res = 1;	 // تهيئة النتيجة
	x = x % p; // p تحديث قيمة هذا المتغير إن كان أكبر من قيمة
				// أو مساويًا له
	while (y > 0) 
	{ 
		// x إن كان العدد فرديًا نضرب النتيجة بالعدد
		if (y & 1) 
			res = (res*x) % p; 

		// y يجب أن يكون العدد
		// زوجيًا الآن
		y = y>>1; // y = y/2 
		x = (x*x) % p; 
	} 
	return res; 
} 

bool miillerTest(int d, int n) 
{ 
	// اختيار عدد عشوائي من النطاق `‎[2, n-2]‎`
	// التأكد من أن العدد المعطى أكبر من 4
	int a = 2 + rand() % (n - 4); 

	//  a^d % n حساب ناتج العملية 
	int x = power(a, d, n); 
	
	if (x == 1 || x == n-1) 
	return true; 
	
	// x الاستمرار في حساب مربع العدد
	// بشرط عدم تحقق أحد الشروط التالية:
	// (i) d لم يصل إلى القيمة n-1 
	// (ii) (x^2) % n لا تساوي 1
	// (iii) (x^2) % n لا تساوي n-1 
	while (d != n-1) 
	{ 
		x = (x * x) % n; 
		d *= 2; 
	
		if (x == 1)	 return false; 
		if (x == n-1) return true; 
	} 
	
	return false; 
} 


bool isPrime(int n, int k) 
{ 
	// الحالات الأساسية
	if (n <= 1 || n == 4) return false; 
	if (n <= 3) return true; 

	// r حساب قيمة
	// n = 2^d * r + 1
	// لبعض قيم r بشرط r >= 1 
	int d = n - 1; 
	while (d % 2 == 0) 
		d /= 2; 
	
	// تنفيذ الحلقة التكرارية
	for (int i = 0; i < k; i++) 
		if (!miillerTest(d, n)) 
			return false; 
	
	return true; 
} 

// اختبار الدوال السابقة
int main() 
{ 
	int k = 4; // عدد الدورات

	cout << "All primes smaller than 100: \n"; 
	for (int n = 1; n < 100; n++) 
	if (isPrime(n, k)) 
		cout << n << " "; 
	
	return 0; 
}

• بايثون:

import random 

# دالة مساعدة لرفع الرقم المعطى إلى قوة معينة ثم حساب باقي القسمة على عدد ثالث 
# It returns (x^y) % p 
def power(x, y, p): 

	# تهيئة النتيجة 
	res = 1 

	# p تحديث قيمة هذا المتغير إن كان أكبر من قيمة
	# أو مساويًا له
	x = x % p
	while (y > 0): 

		# x إن كان العدد فرديًا نضرب النتيجة بالعدد
		if (y & 1): 
			res = (res * x) % p

		# y يجب أن يكون العدد
		# زوجيًا الآن 
		y = y>>1 # y = y/2 
		x = (x * x) % p

	return res

def miillerTest(d, n): 

	# اختيار عدد عشوائي من النطاق `‎[2, n-2]‎` 
	# التأكد من أن العدد المعطى أكبر من 4 
	a = 2 + random.randint(1, n - 4)

	# a^d % n حساب ناتج العملية
	x = power(a, d, n)

	if (x == 1 or x == n - 1): 
		return True

	# x الاستمرار في حساب مربع العدد
	# بشرط عدم تحقق أحد الشروط التالية:
	# (i) d لم يصل إلى القيمة n-1 
	# (ii) (x^2) % n لا تساوي 1
	# (iii) (x^2) % n لا تساوي n-1
	while (d != n - 1): 
		x = (x * x) % n
		d *= 2

		if (x == 1): 
			return False; 
		if (x == n - 1): 
			return True

	return False

def isPrime( n, k): 
	# الحالات الأساسية 
	if (n <= 1 or n == 4): 
		return False
	if (n <= 3): 
		return True

	# r حساب قيمة
	# n = 2^d * r + 1
	# لبعض قيم r بشرط r >= 1 
	d = n - 1
	while (d % 2 == 0): 
		d //= 2

	# تنفيذ الحلقة التكرارية
	for i in range(k): 
		if (miillerTest(d, n) == False): 
			return False

	return True 

# اختبار الدوال السابقة 

# عدد الدورات
k = 4

print("All primes smaller than 100: ")
for n in range(1,100): 
	if (isPrime(n, k)): 
		print(n , end=" ")

• جافا:

import java.io.*; 
import java.math.*; 

class GFG { 

	// دالة مساعدة لرفع الرقم المعطى 
	// إلى قوة معينة ثم حساب باقي القسمة على عدد ثالث 
	static int power(int x, int y, int p) { 
		
		int res = 1; // تهيئة النتيجة
		
		// p تحديث قيمة هذا المتغير إن كان أكبر من قيمة 
		// أو مساويًا له 
		x = x % p; 

		while (y > 0) { 
			
			// x إن كان العدد فرديًا نضرب النتيجة بالعدد 
			if ((y & 1) == 1) 
				res = (res * x) % p; 
		
			// y يجب أن يكون العدد
			// زوجيًا الآن 
			y = y >> 1; // y = y/2 
			x = (x * x) % p; 
		} 
		
		return res; 
	} 
	
	static boolean miillerTest(int d, int n) { 
		
		// اختيار عدد عشوائي من النطاق `‎[2, n-2]‎` 
		// التأكد من أن العدد المعطى أكبر من 4 
		int a = 2 + (int)(Math.random() % (n - 4)); 
	
		// حساب ناتج العملية a^d % n 
		int x = power(a, d, n); 
	
		if (x == 1 || x == n - 1) 
			return true; 
	
		// x الاستمرار في حساب مربع العدد
	// بشرط عدم تحقق أحد الشروط التالية:
		// (i) d لم يصل إلى القيمة n-1 
		// (ii) (x^2) % n لا تساوي 1
		// (iii) (x^2) % n لا تساوي n-1 
		while (d != n - 1) { 
			x = (x * x) % n; 
			d *= 2; 
		
			if (x == 1) 
				return false; 
			if (x == n - 1) 
				return true; 
		} 
	
		return false; 
	} 
	
	static boolean isPrime(int n, int k) { 
		
		// الحالات الأساسية 
		if (n <= 1 || n == 4) 
			return false; 
		if (n <= 3) 
			return true; 
	
		// r حساب قيمة
		// n = 2^d * r + 1 
		// بشرط r >= 1 
		int d = n - 1; 
		
		while (d % 2 == 0) 
			d /= 2; 
	
		// تنفيذ الحلقة التكرارية 
		for (int i = 0; i < k; i++) 
			if (!miillerTest(d, n)) 
				return false; 
	
		return true; 
	} 
	
	// اختبار الدوال السابقة
	public static void main(String args[]) { 
		
		int k = 4; // عدد الدورات 
	
		System.out.println("All primes smaller "
								+ "than 100: "); 
								
		for (int n = 1; n < 100; n++) 
			if (isPrime(n, k)) 
				System.out.print(n + " "); 
	} 
}

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

Output:
All primes smaller than 100: 
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 
61 67 71 73 79 83 89 97

غربال إراتوسثينس

غربال إراتوسثينس Eratosthenes sieve من أكثر الطرق فعالية في إيجاد جميع الأعداد الأولية التي تكون أصغر من n والذي يكون أصغر من 10 ملايين تقريبًا.

تتبع خوارزمية غربال إراتوسثينس الخطوات التالية لإيجاد الأعداد الأولية:

1. إنشاء قائمة بالأعداد الزوجية المتعاقبة والتي تبدأ من 2 وتنتهي بالعدد n.
2. في البداية نفترض أنّ p = 2، وهو أول الأعداد الأولية.
3. نبدأ العدّ من p^2 صعودًا، ونعلّم جميع الأرقام التي تكون أكبر من p^2 أو تساويه في القائمة. هذه الأرقام هي ‎p(p+1), p(p+2), p(p+3)...‎ الخ.
4. العثور على أول رقم غير معلَّم ويكون أكبر من p في القائمة، فإن لم يُعثر على مثل هذا الرقم، تتوقف الخوارزمية عن العمل، وإلاّ نجعل قيمة p مساوية لهذا العدد (وهو العدد الأولي التالي) ثم نعود إلى الخطوة الثالثة.

عند انتهاء عمل الخوارزمية تكون جميع الأعداد غير المعلَّمة في القائمة أعدادًا أولية.

مثال توضيحي:

لنفترض أنّ n = 50. سنطبع جميع الأعداد التي تكون أصغر من 50 أو تساويها.

إنشاء قائمة بالأعداد من 2 إلى 50.

نبدأ بتعليم جميع الأعداد التي تقبل القسمة على 2 والتي تكون أكبر من مربّع 2 أو مساوية له.

ننتقل بعدها إلى العدد غير المعلّم التالي وهو 3 ونعلّم جميع الأعداد التي تكون من مضاعفات 3 وهي في الوقت نفسه أكبر من مربّع 3 أو مساوية له.

ننتقل بعد ذلك إلى العدد غير المعلّم التالي، وهو 5، ونعلّم جميع الأعداد التي تكون من مضاعفات 5 وهي في الوقت نفسه أكبر من مربّع 5 أو مساوية له.

تستمر العملية على هذا المنوال إلى حين الحصول على النتيجة النهائية:

الأعداد الأولية في القائمة هي الأعداد التي بقيت غير معلَّمة حتى نهاية عمل الخوارزمية.

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

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

تستخدم الأمثلة التالية مصفوفة منطقية arr[]‎ حجمها n لتعليم مضاعفات الأعداد الأولية.

• C++‎:

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

void SieveOfEratosthenes(int n) 
{ 
	// إنشاء المصفوفة المنطقية وتهيئة جميع عناصرها لتكون قيمًا صحيحة
	// تكون قيمة العنصر في المصفوفة خاطئة إن كان العدد غير أوليّ
	
	bool prime[n+1]; 
	memset(prime, true, sizeof(prime)); 

	for (int p=2; p*p<=n; p++) 
	{ 
		// إن لم تتغير حالة العدد فهذا يعني أنّه عدد أولي
		if (prime[p] == true) 
		{ 
			// p تحديث جميع مضاعفات العدد
			// والتي تكون أكبر من مربعه أو تساويه
			// p جميع الأعداد التي تكون أصغر من العدد 
			// والتي تكون أصغر من مربعه معلّمة أصلًا
			for (int i=p*p; i<=n; i += p) 
				prime[i] = false; 
		} 
	} 

	// طباعة جميع الأعداد الأولية
	for (int p=2; p<=n; p++) 
	if (prime[p]) 
		cout << p << " "; 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int n = 30; 
	cout << "Following are the prime numbers smaller "
		<< " than or equal to " << n << endl; 
	SieveOfEratosthenes(n); 
	return 0; 
}

• بايثون:

def SieveOfEratosthenes(n): 
	
	# إنشاء المصفوفة المنطقية وتهيئة جميع عناصرها لتكون قيمًا صحيحة
	# تكون قيمة العنصر في المصفوفة خاطئة إن كان العدد غير أوليّ 
	prime = [True for i in range(n+1)] 
	p = 2
	while (p * p <= n): 
		
		# إن لم تتغير حالة العدد فهذا يعني أنّه عدد أولي
		if (prime[p] == True): 
			
			# p تحديث جميع مضاعفات العدد 
			for i in range(p * p, n+1, p): 
				prime[i] = False
		p += 1
	
	# طباعة الأعداد الأولية 
	for p in range(2, n): 
		if prime[p]: 
			print p, 

# اختبار الدالة السابقة
if __name__=='__main__': 
	n = 30
	print "Following are the prime numbers smaller", 
	print "than or equal to", n 
	SieveOfEratosthenes(n)

• جافا:

class SieveOfEratosthenes 
{ 
	void sieveOfEratosthenes(int n) 
	{ 
		// إنشاء المصفوفة المنطقية وتهيئة جميع عناصرها لتكون قيمًا صحيحة
	// تكون قيمة العنصر في المصفوفة خاطئة إن كان العدد غير أوليّ
		boolean prime[] = new boolean[n+1]; 
		for(int i=0;i<n;i++) 
			prime[i] = true; 
		
		for(int p = 2; p*p <=n; p++) 
		{ 
			// إن لم تتغير حالة العدد فهذا يعني أنّه عدد أولي 
			if(prime[p] == true) 
			{ 
				// p تحديث جميع مضاعفات العدد  
				for(int i = p*p; i <= n; i += p) 
					prime[i] = false; 
			} 
		} 
		
		// طباعة الأعداد الأولية 
		for(int i = 2; i <= n; i++) 
		{ 
			if(prime[i] == true) 
				System.out.print(i + " "); 
		} 
	} 
	
	// اختبار الدالة السابقة
	public static void main(String args[]) 
	{ 
		int n = 30; 
		System.out.print("Following are the prime numbers "); 
		System.out.println("smaller than or equal to " + n); 
		SieveOfEratosthenes g = new SieveOfEratosthenes(); 
		g.sieveOfEratosthenes(n); 
	} 
}

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

Following are the prime numbers below 30
2 3 5 7 11 13 17 19 23 29

التعقيد الزمني

يبلغ التعقيد الزمني لخوارزمية غربال إراتوسثينس المقدار O(n*log(log(n)))‎.

الغربال المجزأ

تعاني خوارزمية غربال إراتوسثينس من بعض المشاكل عندما تصبح قيمة n كبيرة:

1. قد لا تتسع الذاكرة لمصفوفة حجمها Θ(n)‎.
2. لا تخزّن هذه الخوارزمية البيانات في الذاكرة الخبيئة Cache عندما تكون قيمة n كبيرة، إذ تتنقل الخوارزمية عبر عناصر المصفوفة دون وجود أي موقعية للإشارة locality of reference.

تقوم خوارزمية الغربال المجزأ على فكرة تقسيم النطاق ‎[0..n-1]‎ إلى أجزاء متعددة وحساب الأعداد الأولية في كل جزء على حدة. تستخدم الخوارزمية في بداية عملها خوارزمية الغربال البسيطة للعثور على الأعداد الأولية التي تكون أصغر من ‎√(n)‎.

يمكن تقسيم طريقة عمل الخوارزمية إلى الخطوات التالية:

1. تستخدم خوارزمية الغربال البسيطة في العثور على جميع الأعداد الأولية التي تكون أصغر من الجذر التربيعي للعدد المعطى أو مساوية له، وتخزين هذه الأعداد الأولية في مصفوفة (لتكن prime[]‎).
2. سنحتاج إلى جميع الأعداد الأولية في النطاق ‎[0..n-1]‎؛ لذا سنقسّم هذا النطاق إلى أجزاء متعددة بشرط أن لا يتجاوز حجم كل جزء المقدار ‎√n.
3. تنفيذ الخطوات التالية على كل جزء [low..high]:
   

أ) إنشاء مصفوفة mark[high-low+1]‎. في هذه الحالة سنحتاج فقط إلى المساحة O(x)‎ إذ تمثل x عدد العناصر في النطاق الحالي.
ب) المرور على جميع الأعداد الأولية التي عُثر عليها في الخطوة الأولى، وتعليم مضاعفات كل عدد أولي في النطاق [low..hight].

تحتاج خوارزمية الغربال البسيطة إلى المساحة O(n)‎ والتي قد تكون غير ملائمة عندما تكون قيمة n كبيرة، أما خوارزمية الغربال المجزّا فتحتاج إلى المساحة O(√n)‎ وتجرى عملية المعالجة على نطاقات أصغر (موقعية الإشارات).

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

• C++‎:

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

// تعثر هذه الدالة على جميع الأعداد الأولية التي تكون أصغر من الحد المعطى
// prime[] باستخدام خوارزمية إراتسوثينس البسيطة، وتخزن النتيجة في المتّجه

void simpleSieve(int limit, vector<int> &prime) 
{ 
	// إنشاء مصفوفة منطقية وتهيئة القيم فيها لتكون جميعها صحيحة.
	// تتحول قيمة العنصر في هذه المصفوفة إلى قيمة خاطئة إذا لم يكن العدد الحالي أوليًا
	// وتتحول إلى قيمة صحيحة إن حصل العكس
	bool mark[limit+1]; 
	memset(mark, true, sizeof(mark)); 

	for (int p=2; p*p<limit; p++) 
	{ 
		//p إن لم تتغير قيمة المتغير
		// فهذا يعني أنّ العدد أوليّ
		if (mark[p] == true) 
		{ 
			// p تحديث جميع مضاعفات العدد
			for (int i=p*2; i<limit; i+=p) 
				mark[i] = false; 
		} 
	} 
	
	// prime طباعة جميع الأعداد الأولية وتخزينها في المصفوفة
	for (int p=2; p<limit; p++) 
	{ 
		if (mark[p] == true) 
		{ 
			prime.push_back(p); 
			cout << p << " "; 
		} 
	} 
} 

// تطبع الدالة جميع الأعداد الأولية التي تكون أصغر من العدد المعطى
void segmentedSieve(int n) 
{ 
	// حساب جميع الأعداد الأولية التي تكون أصغر من الجذر التربيعي للعدد المعطى
	// أو مساوية له وذلك باستخدام خوارزمية الغربال البسيطة
	int limit = floor(sqrt(n))+1; 
	vector<int> prime; 
	simpleSieve(limit, prime); 

	// [0..n-1] تقسيم النطاق
	// إلى أجزاء مختلفة
	// حجم القطعة في هذا المثال يساوي الجذر التربيعي للعدد المعطى
	int low = limit; 
	int high = 2*limit; 

	// [0..n-1] تنفيذ الحلقة التكرارية التالية ما دامت جميع القطع في النطاق
	// لم تعالج بعد.
	// تعالج قطعة واحدة في كل مرة
	while (low < n) 
	{ 
		if (high >= n) 
		high = n; 
		
		// تعليم الأعداد الأولية في النطاق الحالي.
		// mark[i] تصبح القيمة في
		// 'i-low'قيمة خاطئة في النهاية إن كان المقدار
		// عددًا غير أوليّ، وتكون قيمة صحيحة فيما عدا ذلك
		bool mark[limit+1]; 
		memset(mark, true, sizeof(mark)); 

		// استخدام الأعداد الأولية التي عُثر عليها باستخدام الدالة السابقة
		// في العثور على الأعداد الأولية في النطاق الحالي
		for (int i = 0; i < prime.size(); i++) 
		{ 
			// [low..high] إيجاد أصغر عدد في النطاق
			// prime[i] والذي يكون من مضاعفات العدد 
			// على سبيل المثال إن كان الحد الأدنى هو 31
			// prime[i] وكانت 3 هي قيمة
			// فسنبدأ بالعدد 33
			int loLim = floor(low/prime[i]) * prime[i]; 
			if (loLim < low) 
				loLim += prime[i]; 

			/* تعليم مضاعفات العدد الأولي في النطاق:
			j - low يجري تعليم العدد
			j مقابل العدد
			[low, high] بمعنى أن كل عدد في النطاق
			[0, high-low] سيرتبط بالنطاق 
			لهذا إن كان النطاق ‎[50, 100]‎ فإن تعليم العدد 50
			يعني تعليم العدد 0، والعدد 51 يعني تعليم العدد 1 وهكذا
			بهذه الطريقة سيحتاج النطاق إلى حجز نصف المساحة في الذاكرة فقط */
			for (int j=loLim; j<high; j+=prime[i]) 
				mark[j-low] = false; 
		} 

		// الأعداد التي لم تعلم بقيمة خاطئة هي أعداد أولية
		for (int i = low; i<high; i++) 
			if (mark[i - low] == true) 
				cout << i << " "; 

		// تحديث القيمة الدنيا والعظمى للنطاق من أجل الدورة التالية
		low = low + limit; 
		high = high + limit; 
	} 
} 

// اختبار الدوال السابقة
int main() 
{ 
	int n = 100; 
	cout << "Primes smaller than " << n << ":n"; 
	segmentedSieve(n); 
	return 0; 
}

• بايثون:

import math 
prime = [] 

# تعثر هذه الدالة على جميع الأعداد الأولية التي تكون أصغر من الحد المعطى
# prime[] باستخدام خوارزمية إراتسوثينس البسيطة، وتخزن النتيجة في المتّجه

def simpleSieve(limit): 
	
	# إنشاء مصفوفة منطقية وتهيئة القيم فيها لتكون جميعها صحيحة.
	# تتحول قيمة العنصر في هذه المصفوفة إلى قيمة خاطئة إذا لم يكن العدد الحالي أوليًا
	# وتتحول إلى قيمة صحيحة إن حصل العكس
	mark = [True for i in range(limit + 1)] 
	p = 2
	while (p * p <= limit): 
		
		# p إن لم تتغير قيمة المتغير
		# فهذا يعني أنّ العدد أوليّ 
		if (mark[p] == True): 
			
			# p تحديث جميع مضاعفات العدد 
			for i in range(p * p, limit + 1, p): 
				mark[i] = False
		p += 1
		
	# prime طباعة جميع الأعداد الأولية وتخزينها في المصفوفة 
	for p in range(2, limit): 
		if mark[p]: 
			prime.append(p) 
			print(p,end = " ") 
			
# تطبع الدالة جميع الأعداد الأولية التي تكون أصغر من العدد المعطى 
def segmentedSieve(n): 
	
	# حساب جميع الأعداد الأولية التي تكون أصغر من الجذر التربيعي للعدد المعطى
	# أو مساوية له وذلك باستخدام خوارزمية الغربال البسيطة 
	limit = int(math.floor(math.sqrt(n)) + 1) 
	simpleSieve(limit) 
	
	# [0..n-1] تقسيم النطاق
	# إلى أجزاء مختلفة
	# حجم القطعة في هذا المثال يساوي الجذر التربيعي للعدد المعطى 
	low = limit 
	high = limit * 2
	
	# [0..n-1] تنفيذ الحلقة التكرارية التالية ما دامت جميع القطع في النطاق
	# لم تعالج بعد.
	# تعالج قطعة واحدة في كل مرة 
	while low < n: 
		if high >= n: 
			high = n 
			
		# تعليم الأعداد الأولية في النطاق الحالي.
		# mark[i] تصبح القيمة في
		# 'i-low'قيمة خاطئة في النهاية إن كان المقدار
		# عددًا غير أوليّ، وتكون قيمة صحيحة فيما عدا ذلك 
		mark = [True for i in range(limit + 1)] 
		
		# استخدام الأعداد الأولية التي عُثر عليها باستخدام الدالة السابقة
		# في العثور على الأعداد الأولية في النطاق الحالي 
		for i in range(len(prime)): 
			
			# [low..high] إيجاد أصغر عدد في النطاق
			# prime[i] والذي يكون من مضاعفات العدد 
			# على سبيل المثال إن كان الحد الأدنى هو 31
			# prime[i] وكانت 3 هي قيمة
			# فسنبدأ بالعدد 33. 
			loLim = int(math.floor(low / prime[i]) *
										prime[i]) 
			if loLim < low: 
				loLim += prime[i] 
				
			# تعليم مضاعفات العدد الأولي في النطاق:
			# j - low يجري تعليم العدد
			# j مقابل العدد
			# [low, high] بمعنى أن كل عدد في النطاق
			# [0, high-low] سيرتبط بالنطاق 
			# لهذا إن كان النطاق ‎[50, 100]‎ فإن تعليم العدد 50
			# يعني تعليم العدد 0، والعدد 51 يعني تعليم العدد 1 وهكذا
			# بهذه الطريقة سيحتاج النطاق إلى حجز نصف المساحة في الذاكرة فقط
			for j in range(loLim, high, prime[i]): 
				mark[j - low] = False
				
		# الأعداد التي لم تعلم بقيمة خاطئة هي أعداد أولية 
		for i in range(low, high): 
			if mark[i - low]: 
				print(i, end = " ") 
				
		# تحديث القيمة الدنيا والعظمى للنطاق من أجل الدورة التالية 
		low = low + limit 
		high = high + limit 

# اختبار الدوال السابقة 
n = 100
print("Primes smaller than", n, ":") 
segmentedSieve(100)

• جافا:

import java.util.Vector; 
import static java.lang.Math.sqrt; 
import static java.lang.Math.floor; 

class Test 
{ 
	// تعثر هذه الدالة على جميع الأعداد الأولية التي تكون أصغر من الحد المعطى
	// prime[] باستخدام خوارزمية إراتسوثينس البسيطة، وتخزن النتيجة في المتّجه
	static void simpleSieve(int limit, Vector<Integer> prime) 
	{ 
		// إنشاء مصفوفة منطقية وتهيئة القيم فيها لتكون جميعها صحيحة.
		// تتحول قيمة العنصر في هذه المصفوفة إلى قيمة خاطئة إذا لم يكن العدد الحالي أوليًا
		// وتتحول إلى قيمة صحيحة إن حصل العكس 
		boolean mark[] = new boolean[limit+1]; 
		
		for (int i = 0; i < mark.length; i++) 
			mark[i] = true; 
	
		for (int p=2; p*p<limit; p++) 
		{ 
			//p إن لم تتغير قيمة المتغير
			// فهذا يعني أنّ العدد أوليّ
			if (mark[p] == true) 
			{ 
				// p تحديث جميع مضاعفات العدد
				for (int i=p*2; i<limit; i+=p) 
					mark[i] = false; 
			} 
		} 
	
		// prime طباعة جميع الأعداد الأولية وتخزينها في  
		for (int p=2; p<limit; p++) 
		{ 
			if (mark[p] == true) 
			{ 
				prime.add(p); 
				System.out.print(p + " "); 
			} 
		} 
	} 
	
	// تطبع الدالة جميع الأعداد الأولية التي تكون أصغر من العدد المعطى 
	static void segmentedSieve(int n) 
	{ 
		// حساب جميع الأعداد الأولية التي تكون أصغر من الجذر التربيعي للعدد المعطى
		// أو مساوية له وذلك باستخدام خوارزمية الغربال البسيطة 
		int limit = (int) (floor(sqrt(n))+1); 
		Vector<Integer> prime = new Vector<>(); 
		simpleSieve(limit, prime); 
	
		// [0..n-1] تقسيم النطاق
		// إلى أجزاء مختلفة
		// حجم القطعة في هذا المثال يساوي الجذر التربيعي للعدد المعطى 
		int low = limit; 
		int high = 2*limit; 
	
		// [0..n-1] تنفيذ الحلقة التكرارية التالية ما دامت جميع القطع في النطاق 
		// لم تعالج بعد.
		// تعالج قطعة واحدة في كل مرة
		while (low < n) 
		{ 
			if (high >= n) 
				high = n; 

			// تعليم الأعداد الأولية في النطاق الحالي.
			// mark[i] تصبح القيمة في
			// 'i-low'قيمة خاطئة في النهاية إن كان المقدار
			// عددًا غير أوليّ، وتكون قيمة صحيحة فيما عدا ذلك 
			boolean mark[] = new boolean[limit+1]; 
			
			for (int i = 0; i < mark.length; i++) 
				mark[i] = true; 
	
			// استخدام الأعداد الأولية التي عُثر عليها باستخدام الدالة السابقة
			// في العثور على الأعداد الأولية في النطاق الحالي
			for (int i = 0; i < prime.size(); i++) 
			{ 
				// [low..high] إيجاد أصغر عدد في النطاق
				// prime[i] والذي يكون من مضاعفات العدد 
				// على سبيل المثال إن كان الحد الأدنى هو 31
				// prime[i] وكانت 3 هي قيمة
				// فسنبدأ بالعدد 33 
				int loLim = (int) (floor(low/prime.get(i)) * prime.get(i)); 
				if (loLim < low) 
					loLim += prime.get(i); 
	
				/* تعليم مضاعفات العدد الأولي في النطاق:
				j - low يجري تعليم العدد
				j مقابل العدد
				[low, high] بمعنى أن كل عدد في النطاق
				[0, high-low] سيرتبط بالنطاق 
				لهذا إن كان النطاق ‎[50, 100]‎ فإن تعليم العدد 50
				يعني تعليم العدد 0، والعدد 51 يعني تعليم العدد 1 وهكذا
				بهذه الطريقة سيحتاج النطاق إلى حجز نصف المساحة في الذاكرة فقط */
				for (int j=loLim; j<high; j+=prime.get(i)) 
					mark[j-low] = false; 
			} 
	
			// الأعداد التي لم تعلم بقيمة خاطئة هي أعداد أولية 
			for (int i = low; i<high; i++) 
				if (mark[i - low] == true) 
					System.out.print(i + " "); 
	
			// تحديث القيمة الدنيا والعظمى للنطاق من أجل الدورة التالية 
			low = low + limit; 
			high = high + limit; 
		} 
	} 
	
	// اختبار الدوال السابقة 
	public static void main(String args[]) 
	{ 
		int n = 100; 
		System.out.println("Primes smaller than " + n + ":"); 
		segmentedSieve(n); 
	} 
}

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

Primes smaller than 100:
2 3 5 7 11 13 17 19 23 29 31 37 41
43 47 53 59 61 67 71 73 79 83 89 97

التعقيد الزمني

التعقيد الزمني لهذه الخوارزمية مماثل للتعقيد الزمني لخوارزمية غربال إراتوسثينس، ولكنّ خوارزمية الغربال المجزأ تتفوق عى الأخيرة عند التعامل مع قيم n الكبيرة.

مصادر

• صفحة Prime Numbers في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Primality Test | Set 1 (Introduction and School Method)‎ في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Primality Test | Set 2 (Fermat Method)‎ في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Primality Test | Set 3 (Miller–Rabin)‎ في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Sieve of Eratosthenes في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Segmented Sieve في توثيق الخوارزميات في موقع GeeksforGeeks.