غربال إراتوستينس
غربال إراتوستينس هي خوارزمية بسيطة لإيجاد جميع الأعداد الأولية حتى عدد ما. تعمل هذه الخوارزمية بكفاءة من أجل الأعداد الأولية الصغيرة (حتى 10 مليون). صممت هذه الخوارزمية من قبل إراتوستينس الرياضياتي الإغريقي.
الخوارزمية
لإيجاد الأعداد الأولية الأصغر من n تتبع الخوارزمية الخطوات التالية:
- أنشئ قائمة بجميع الأعداد من الرقم 2 إلى العدد الذي تريد الأعظم
- نبدأ بقيمة لـ p تساوي 2، أول الأعداد الأولية
- اشطب من القائمة جميع الأعداد من مضاعفات p والتي هي أكبر من p
- ابحث عن العدد التالي الغير مشطوب في القائمة، هذا العدد هو العدد الأولي التالي، وسيكون هو العدد p التالي
- كرر الخطوات 3 و 4 حتى p2 هي أكبر من n
- جميع الأعداد الباقية على القائمة هي أعداد أولية.
bg:Решето на Ератостен bs:Eratostenovo sito ca:Sedàs d'Eratòstenes cs:Eratosthenovo síto da:Eratosthenes' si de:Sieb des Eratosthenes el:Κόσκινο του Ερατοσθένη Sieve of Eratosthenes]] eo:Kribrilo de Eratosteno es:Criba de Eratóstenes fa:غربال اراتوستن fi:Eratostheneen seula fr:Crible d'Ératosthène he:הנפה של ארטוסתנס hr:Eratostenovo sito hu:Eratoszthenész szitája id:Saringan Eratosthenes it:Crivello di Eratostene ja:エラトステネスの篩 ka:ერატოსთენეს საცერი ko:에라토스테네스의 체 la:Cribratum Eratosthenis lt:Eratosteno rėtis lv:Eratostena siets mk:Ератостеново сито nl:Zeef van Eratosthenes no:Eratosthenes' sil pl:Sito Eratostenesa pms:Siass d'Eratòstene pt:Crivo de Eratóstenes ro:Ciurul lui Eratostene ru:Решето Эратосфена scn:Criveddu d'Eratòstini sh:Eratostenovo sito simple:Sieve of Eratosthenes sk:Eratostenovo sito sl:Eratostenovo sito sq:Sita e Eratostenit sr:Ератостеново сито sv:Eratosthenes såll tr:Eratosten kalburu uk:Решето Ератосфена vi:Sàng Eratosthenes zh:埃拉托斯特尼筛法
