منخل إيراتوسثينيز ( Sieve of Eratosthenes )

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

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

ابتداءً من 3، العدد التالي غير المخطط بعد 2، ضع خطًا مائلاً على كل رقم ثالث. عد واحصر الأعداد التي لم تمر عبر المنخل، وكذلك التي مرت. يؤدي ذلك إلى حذف الأعداد التي تقبل القسمة المتساوية على 3 فيما عدا 3 ذاتها. وبمواصلة هذه العملية مع العدد الأكبر التالي غير المعلم، تبقى لدينا الأعداد الأولية فقط.

نوضح فيما يلي مثالاً لمنخل إيراتوسثينيز ويبين هذا المثال أن 2، 3، 5 هي الأعداد الثلاثة الأولية الأولى:

في الخطوة التالية نبدأ بالعدد 5 ونشطب كل عدد خامس وهذه العملية لا نهاية لها، حيث لا يوجد عدد أولي نهائي.