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

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

ابدأ بافتراض أن كل عدد أولي. ثم اشطب مضاعفات كل عدد أولي تعثر عليه، لتبقي الأعداد الأولية الحقيقية فقط.

أنشئ قائمة منطقية يحدّد فيها الفهرس i ما إذا كان i أوليًا. هذه المصفوفة هي اللوحة التي يرسم عليها الغربال.

زد قيمة i تدريجيًا. وفي أول مرة تصل فيها إلى عدد لا تزال علامته True، فلا بد أن يكون أوليًا جديدًا لا يملك عاملًا أصغر منه.

لكل عدد أولي i، ضع علامة تفيد بأن 2i و3i و4i وما إلى ذلك ليست أولية. فمن الواضح أن تلك المضاعفات تقبل i قاسمًا لها.

ابدأ الشطب عند i*i، لا عند 2i. فقد أزيلت كل مضاعفة أصغر من ذلك بواسطة عدد أولي أسبق، لذا تخطّها.

لا تحتاج إلى تشغيل الغربال إلا ما دام i*i لا يتجاوز N. فبعد الجذر التربيعي تكون كل علامة True متبقية لعدد أولي بالفعل.

اجمع بين المسح الخارجي وعملية الشطب الداخلية. بعد انتهاء الحلقة، يكون كل فهرس لا تزال علامته True عددًا أوليًا مؤكدًا.

حوّل العلامات النهائية إلى قائمة باستخدام استيعاب القائمة. والآن لديك كل عدد أولي حتى N، جاهزًا للاستعلامات السريعة.

يعمل الغربال في زمن يقارب O(n log log n)، أي شبه خطي. ولهذا يتفوق كثيرًا على الاختبار المتكرر لكل عدد على حدة.

تستخدم مصفوفة العلامات ذاكرة تتناسب مع N. وعند التعامل مع حدود كبيرة جدًا، راقب ميزانية المساحة قبل التخصيص.

تذكّر التحسين الصغير في الحلقة الداخلية.

يمكنك الآن إنشاء غربال لسرد جميع الأعداد الأولية حتى N في زمن شبه خطي، مع بدء كل عدد أولي عند i*i والتوقف عند الجذر. ✅