منخل إراتوستينس في Python & C++
سارة تشين
⚡ ملخص ذكي
غربال إراتوستينس هو خوارزمية كلاسيكية للأعداد الأولية تقوم بتصفية الأعداد المركبة عن طريق وضع علامات متكررة على مضاعفات كل عدد أولي، تاركة فقط الأعداد الأولية ضمن حد أعلى مختار للبحث السريع.
ما هو منخل إراتوستينس؟
غربال إراتوستينس هو أبسط غربال للأعداد الأولية. وهو خوارزمية تُستخدم لاكتشاف جميع الأعداد الأولية ضمن حدٍّ مُحدد. توجد عدة غربال للأعداد الأولية، منها غربال إراتوستينس، وغربال أتكين، وغربال سوندارام.
الكلمة "غرباليشير مصطلح "المنخل" إلى أداة تُستخدم لتصفية المواد. وبالمثل، فإن خوارزمية المنخل في Python وتشير عبارة "وغيرها من اللغات" إلى طريقة تقوم بتصفية الأعداد الأولية من قائمة الأعداد الصحيحة.
تستخدم هذه الخوارزمية أسلوبًا تكراريًا لتصفية الأعداد الأولية. تبدأ عملية التصفية بأصغر عدد أولي. العدد الأولي هو عدد طبيعي أكبر من 1 ولا يقبل القسمة إلا على عددين، وهما 1 والعدد نفسه. Numbers الأعداد التي ليست أعدادًا أولية تسمى أعدادًا مركبة.
لماذا نستخدم منخل إراتوستينس؟
في طريقة غربال إراتوستينس، يُختار عدد أولي صغير أولاً، ثم تُستبعد جميع مضاعفاته. وتُنفذ العملية في حلقة تكرارية ضمن نطاق محدد، مُنتجةً جميع الأعداد الأولية حتى العدد n بكفاءة دون إجراء قسمة تجريبية على كل عدد مرشح.
هذا يجعل الغربال أسرع من التحقق من أولية عدد واحد في كل مرة. ويُستخدم على نطاق واسع في نظرية الأعداد، وعلم التشفير، والتجزئة، والبرمجة التنافسية حيث يجب توليد العديد من الأعداد الأولية بسرعة.
فمثلا:
لنأخذ نطاق الأرقام من 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. إذن، ن = 25.
الخطوة 1) في الخطوة الأولى، سنأخذ قائمة من الأرقام من 2 إلى 25 لأننا اخترنا n = 25.
الخطوة 2) ثم نختار أصغر عدد في القائمة، وهو س. في البداية، س = ٢ لأنه أصغر عدد أولي. ثم نمر على القائمة ونحدد مضاعفات العدد ٢.
مضاعفات العدد 2 للقيمة المعطاة لـ n هي: 4، 6، 8، 10، 12، 14، 16، 18، 20، 22، 24.
ملاحظة: يشير اللون الأزرق إلى الرقم المحدد، بينما يشير اللون الوردي إلى المضاعفات المستبعدة.
الخطوة 3) ثم نختار الرقم الأصغر التالي غير المحدد، وهو 3، ونكرر الخطوة الأخيرة بوضع علامة على مضاعفات الرقم 3.
الخطوة 4) نكرر الخطوة 3 بنفس الطريقة حتى x = 
أو شنومكس.
الخطوة 5) أما الأرقام المتبقية غير المميزة فهي الأعداد الأولية من 2 إلى 25.
مستعار-Code
يلتقط الكود الزائف التالي البنية الأساسية لغربال إراتوستينس قبل أن نترجمه إلى كود فعلي.
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++ Code مثال
فيما يلي صورة كاملة 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 مثال البرنامج
ما يلي Python ينفذ البرنامج نفس الخوارزمية باستخدام قائمة منطقية وحلقة تكرارية (while).
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 أكبر.
يمكن تحسين الخوارزمية من خلال تقديم بعض الميزات الجديدة. والفكرة هي تقسيم نطاق الأرقام إلى أجزاء أصغر وحساب الأعداد الأولية في تلك الأجزاء واحدًا تلو الآخر. وهذه طريقة فعّالة لتقليل تعقيد المساحة. وتسمى هذه الطريقة غربال مجزأة.
يمكن تحقيق التحسين بالطريقة التالية:
- استخدم منخلًا بسيطًا للعثور على الأعداد الأولية من 2 إلى
وتخزينها في مجموعة. - قم بتقسيم النطاق [0…n-1] إلى أجزاء متعددة بالحجم على الأكثر .
- لكل جزء، قم بالمرور عليه وتحديد مضاعفات الأعداد الأولية التي تم العثور عليها في الخطوة 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))).
بعد ذلك، ستتعرف على مثلث باسكال.
