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

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

1. أنشئ قائمة بجميع الأعداد من الرقم 2 إلى العدد الذي تريد,
2. نبدأ بقيمة ل p تساوي 2، أول الأعداد الأولية,
3. اشطب من القائمة جميع الأعداد من مضاعفات p والتي هي أكبر من p,
4. ابحث عن العدد التالي غير المشطوب في القائمة، هذا العدد هو العدد الأولي التالي، وسيكون هو العدد p التالي,
5. كرر الخطوات 3 و4 حتى يصير p² هي أكبر من n,
6. جميع الأعداد الباقية على القائمة هي أعداد أولية.

المدخل: عدد 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 هي أعداد أولية.

انظر برهان صيغة جداء أويلر بالنسبة لدالة زيتا لريمان.

• غربال أتكين,

• بوابة خوارزميات
• بوابة علم الحاسوب
• بوابة نظرية الأعداد