غربال خوارزمية إراتوستينس: Python, C++ مثال

منخل إراتوستينس هو أبسط منخل للأعداد الأولية. إنه خوارزمية للأعداد الأولية للبحث عن جميع الأعداد الأولية في حد معين. هناك العديد من مناخل الأعداد الأولية. على سبيل المثال - منخل إراتوستينس، منخل أتكين، منخل سوندارام، إلخ.

الكلمة "غربال"يعني أداة تقوم بتصفية المواد. وهكذا، فإن خوارزمية الغربال في Python وتشير اللغة الإنجليزية واللغات الأخرى إلى خوارزمية لتصفية الأعداد الأولية.

تقوم هذه الخوارزمية بتصفية الأعداد الأولية بطريقة تكرارية. تبدأ عملية التصفية بأصغر عدد أولي. العدد الأولي هو عدد طبيعي أكبر من 1 وله قواسمان فقط، أي 1 والعدد نفسه. الأعداد التي ليست أعدادًا أولية تسمى الأعداد المركبة.

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

فمثلا:

لنأخذ نطاق الأرقام من 2 إلى 10.

بعد تطبيق غربال إراتوستينس، سيتم إنتاج قائمة الأعداد الأولية 2، 3، 5، 7

خوارزمية غربال إراتوستينس

فيما يلي خوارزمية غربال إراتوستينس:

الخطوة 1) أنشئ قائمة من الأعداد من 2 إلى النطاق المحدد n. نبدأ بالعدد 2 لأنه أصغر وأول عدد أولي.

الخطوة 2) قم بتحديد أصغر رقم في القائمة، x (في البداية x يساوي 2)، ثم قم بالمرور عبر القائمة، وقم بتصفية الأرقام المركبة المقابلة عن طريق وضع علامة على جميع مضاعفات الأرقام المحددة.

الخطوة 3) ثم اختر العدد الأولي التالي أو أصغر رقم غير محدد في القائمة وكرر الخطوة 2.

الخطوة 4) كرر الخطوة السابقة حتى تكون قيمة x أقل من أو تساوي الجذر التربيعي لـ n (x<=).

ملحوظة: المنطق الرياضي بسيط للغاية. يمكن تحليل نطاق الأرقام n إلى عوامل -

ن=أ*ب

مرة أخرى، ن =*

= (العامل أصغر من ) * (العامل أكبر من )

لذلك على الأقل واحد من العوامل الرئيسية أو يجب أن يكون كلاهما <=. وهكذا العبور إلى سيكون كاف.

الخطوة 5) بعد هذه الخطوات الأربع، ستكون الأرقام غير المميزة المتبقية هي كل الأعداد الأولية في النطاق المحدد n.

على سبيل المثال:

دعونا نأخذ مثالا ونرى كيف يعمل.

في هذا المثال، سنجد قائمة الأعداد الأولية من 2 إلى 25. لذا، n=25.

الخطوة 1) في الخطوة الأولى، سنأخذ قائمة من الأرقام من 2 إلى 25 حيث اخترنا n=25.

الخطوة 2) ثم نختار أصغر رقم في القائمة، x. في البداية x=2 لأنه أصغر عدد أولي. ثم ننتقل عبر القائمة ونضع علامة على مضاعفات الرقم 2.

مضاعفات 2 لقيمة n المعطاة هي: 4، 6، 8، 10، 12، 14، 16، 18، 20، 22، 24.

ملحوظة: اللون الأزرق يدل على الرقم المحدد، واللون الوردي يدل على المضاعفات المحذوفة

الخطوة 3) ثم نختار الرقم الأصغر التالي غير المحدد، وهو 3، ونكرر الخطوة الأخيرة بوضع علامة على مضاعفات الرقم 3.

الخطوة 4) نكرر الخطوة 3 بنفس الطريقة حتى x= أو شنومكس.

الخطوة 5) أما الأعداد غير المميزة المتبقية فستكون الأعداد الأولية من 2 إلى 25.

كود مزيف

Begin
	Declare a boolean array of size n and initialize it to true
	For all numbers i : from 2 to sqrt(n)
     		IF bool value of i is true THEN
         			i is prime
         			For all multiples of i (i<n)
             			mark multiples of i as composite
Print all unmarked numbers
End

غربال إراتوستينس ج/C++ مثال الكود

#include <iostream>
#include <cstring>
using namespace std;
void Sieve_Of_Eratosthenes(int n)
{
    // Create and initialize a boolean array
    bool primeNumber[n + 1];
    memset(primeNumber, true, sizeof(primeNumber));
    for (int j = 2; j * j <= n; j++) {
        if (primeNumber[j] == true) {
            // Update all multiples of i as false
            for (int k = j * j; k <= n; k += j)
                primeNumber[k] = false;
        }
    } 
    for (int i = 2; i <= n; i++)
        if (primeNumber[i])
            cout << i << " ";
}
int main()
{
    int n = 25;
    Sieve_Of_Eratosthenes(n);
    return 0;
} 

الإخراج:

2 3 5 7 11 13 17 19 23

منخل إراتوستينس Python مثال البرنامج

def SieveOfEratosthenes(n):
# Create a boolean array
	primeNumber = [True for i in range(n+2)]
	i = 2
	while (i * i <= n):
		if (primeNumber[i] == True):
			# Update all multiples of i as false
			for j in range(i * i, n+1, i):
				primeNumber[j] = False
		i += 1
	for i in range(2, n):
		if primeNumber[i]:
			print(i)
n = 25
SieveOfEratosthenes(n)

الإخراج:

2
3
5
7
11
13
17
19
23

غربال مجزأ

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

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

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

1. استخدم منخلًا بسيطًا للعثور على الأعداد الأولية من 2 إلى وتخزينها في مجموعة.
2. قم بتقسيم النطاق [0…n-1] إلى أجزاء متعددة بالحجم على الأكثر
3. بالنسبة لكل جزء، كرر خلال الجزء وحدد مضاعفات الأعداد الأولية الموجودة في الخطوة 1. تتطلب هذه الخطوة O() كحد أقصى.

يتطلب الغربال العادي مساحة ذاكرة مساعدة O(n)، بينما يتطلب الغربال المجزأ O()، وهو تحسن كبير بالنسبة لقيمة n كبيرة. كما أن لهذه الطريقة جانبًا سلبيًا أيضًا لأنها لا تعمل على تحسين التعقيد الزمني.

تحليل التعقيد

تعقيد الفضاء:

يتطلب الغربال البسيط لخوارزمية إراتوستينس مساحة ذاكرة O(n). ويتطلب الغربال المجزأ
O() المساحة المساعدة.

تعقيد الوقت:

إن التعقيد الزمني لخوارزمية غربال إراتوستينس المنتظم هو O(n*log(log(n))). وسيتم مناقشة السبب وراء هذا التعقيد أدناه.

بالنسبة لعدد معين n، فإن الوقت المطلوب لتحديد عدد مركب (أي الأعداد غير الأولية) ثابت. لذا، فإن عدد مرات تشغيل الحلقة يساوي-

ن/2 + ن/3 + ن/5 + ن/7 + ……∞

= ن* (1/2 + 1/3 + 1/5 + 1/7 +…….∞)

يمكن خصم التقدم التوافقي لمجموع الأعداد الأولية كـ log(log(n)).

(1/2 + 1/3 + 1/5 + 1/7 +…….∞) = سجل(سجل(ن))

لذا، فإن تعقيد الوقت سيكون-

T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)

= ن * سجل (سجل (ن))

وبالتالي فإن تعقيد الوقت O(n * log(log(n)))

التالي سوف تتعلم عن مثلث باسكال

الملخص

• يقوم غربال إراتوستينس بتصفية الأعداد الأولية الموجودة في الحد الأعلى المحدد.
• تبدأ تصفية الأعداد الأولية من أصغر عدد أولي وهو "2". ويتم ذلك بشكل متكرر.
• يتم التكرار حتى الجذر التربيعي لـ n، حيث n هو نطاق الأرقام المحدد.
• بعد هذه التكرارات، الأعداد المتبقية هي الأعداد الأولية.