غربال إراتوستينس للأعداد الأولية

أدخل العدد N الذي تريد إيجاد عدد الأعداد الأولية التي تساويه أو أقل. على سبيل المثال، إذا كان N = 100، فسيتم حساب عدد الأعداد الأولية من 2 إلى 100.

تقوم الخوارزمية بإنشاء قائمة بجميع الأعداد من 2 إلى N. يتم اعتبار جميع الأعداد كأولية في البداية، ثم يتم وضع علامة على مضاعفات كل عدد أولي بدءًا من 2. على سبيل المثال، نبدأ بـ 2 ونحدد مضاعفاته (4، 6، 8، ...) كأعداد غير أولية.

ننتقل إلى العدد التالي الذي لم يتم وضع علامة عليه (وهو عدد أولي). على سبيل المثال، بعد 2، العدد التالي هو 3. نضع علامة على مضاعفات 3 (6، 9، 12، ...) مع ملاحظة أن 6 تم تحديدها بالفعل.

نستمر هذه العملية حتى نصل إلى الجذر التربيعي لـ N. وذلك لأن أي عدد غير أولي له عامل أولي يساوي أو أقل من جذره التربيعي. بعد الانتهاء، الأعداد المتبقية غير المحددة هي الأعداد الأولية.