الغربال

التعليمات

مهمتك هي إنشاء برنامج ينفّذ خوارزمية غربال إراتوستينس لإيجاد جميع الأعداد الأولية الأصغر من عدد معيّن أو المساوية له.

العدد الأولي هو عدد أكبر من 1 لا يقبل القسمة إلا على 1 وعلى نفسه. على سبيل المثال، الأعداد 2 و3 و5 و7 و11 و13 أعداد أولية. في المقابل، العدد 6 ليس عددًا أوليًا، لأنه لا يقبل القسمة على 1 وعلى نفسه فحسب، بل أيضًا على 2 و3.

لاستخدام غربال إراتوستينس، عليك أولًا إنشاء مصفوفة بجميع الأعداد بين 2 والعدد المعيّن. ثم تكرّر الخطوات التالية:

1. ابحث عن العدد التالي غير المعلَّم في مصفوفتك (مع تخطّي الأعداد المعلَّمة). هذا العدد أولي.
2. علّم جميع مضاعفات ذلك العدد الأولي بأنها غير أولية.

تستمر في تكرار هذه الخطوات حتى تمرّ على كل عدد في مصفوفتك. وفي النهاية، تكون جميع الأعداد غير المعلَّمة أعدادًا أولية.

مثال

لنفترض أنك تبحث عن الأعداد الأولية الأصغر من العدد 10 أو المساوية له.

• اكتب الأعداد 2 و3 و4 و5 و6 و7 و8 و9 و10، واتركها كلها غير معلَّمة.
• العدد 2 غير معلَّم، لذا هو عدد أولي. علّم الأعداد 4 و6 و8 و10 بأنها "غير أولية".
• العدد 3 غير معلَّم، لذا هو عدد أولي. علّم العددين 6 و9 بأنهما غير أوليين (تعليم العدد 6 اختياري، فهو معلَّم بالفعل).
• العدد 4 معلَّم بأنه "غير أولي"، لذا نتخطّاه.
• العدد 5 غير معلَّم، لذا هو عدد أولي. علّم العدد 10 بأنه غير أولي (اختياري، فهو معلَّم بالفعل).
• العدد 6 معلَّم بأنه "غير أولي"، لذا نتخطّاه.
• العدد 7 غير معلَّم، لذا هو عدد أولي.
• العدد 8 معلَّم بأنه "غير أولي"، لذا نتخطّاه.
• العدد 9 معلَّم بأنه "غير أولي"، لذا نتخطّاه.
• العدد 10 معلَّم بأنه "غير أولي"، لذا نتوقف لأنه لم تبقَ أعداد أخرى لفحصها.

لقد فحصت جميع الأعداد ووجدت أن الأعداد 2 و3 و5 و7 ما زالت غير معلَّمة، وهذا يعني أنها الأعداد الأولية الأصغر من العدد 10 أو المساوية له.

---

المصدر

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