غربال إراتوستينس هي خوارزمية بسيطة لإيجاد جميع الأعداد الأولية حتى عدد ما.[1][2][3] تعمل هذه الخوارزمية بكفاءة من أجل الأعداد الأولية الصغيرة (حتى عشرة ملايين). صممت هذه الخوارزمية من قبل إراتوستينس الرياضياتي الإغريقي.
وصف الخوارزمية
لإيجاد الأعداد الأولية الأصغر من n تتبع الخوارزمية الخطوات التالية:
- أنشئ قائمة بجميع الأعداد من الرقم 2 إلى العدد الذي تريد,
- نبدأ بقيمة ل p تساوي 2، أول الأعداد الأولية,
- اشطب من القائمة جميع الأعداد من مضاعفات p والتي هي أكبر من p,
- ابحث عن العدد التالي غير المشطوب في القائمة، هذا العدد هو العدد الأولي التالي، وسيكون هو العدد p التالي,
- كرر الخطوات 3 و4 حتى يصير p2 هي أكبر من n,
- جميع الأعداد الباقية على القائمة هي أعداد أولية.
مثال
تعقيد الخوارزمية
البرمجة
المدخل: عدد n طبيعي أكبر قطعا من 1
ليكن A جدولا من القيم البوليانية، مفهرسا بالأعداد الطبيعية من
2 حتى n، كلها تساوي في البداية ل true.
for i = 2, 3, 4, ...
, while i ≤ n/2:
if A[i] is true:
for j = 2i, 3i, 4i, ..., while j ≤ n:
A[j] = false
الآن كل الأعداد i حيث [A[i تساوي true هي أعداد أولية.
المتتاليات الحسابية
غربال أويلر
انظر برهان صيغة جداء أويلر بالنسبة لدالة زيتا لريمان.
انظر أيضا
مراجع
