Ready to put your newfound language skills into use? Get 40% off CodeCrafter's real-world proficiency projects!

احصل على خصمك

المسارات

COBOL

التمارين

الغربال

متوسط

مقدمة

اشتريت صندوقًا كبيرًا من قطع الحاسوب العشوائية في سوق لبيع الأغراض المستعملة. وقد بدأت تجمع القطع معًا لتبني حواسيب مخصّصة.

تريد أن تختبر أداء توليفات مختلفة من القطع، فقررت إنشاء برنامج لقياس الأداء خاص بك، لترى كيف يتفاوت أداء حواسيبك. واخترت خوارزمية "Sieve of Eratosthenes" الشهيرة، وهي خوارزمية قديمة، لكنها ستدفع حواسيبك إلى أقصى حدودها.

التعليمات

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

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

لاستخدام غربال إراتوستينس، اكتب أولًا جميع الأعداد من 2 حتى العدد المعطى شاملًا إياه. ثم اتبع هذه الخطوات:

ابحث عن العدد التالي غير المعلَّم (متجاوزًا الأعداد المعلَّمة). هذا العدد أولي.
علّم جميع مضاعفات ذلك العدد الأولي بأنها ليست أولية.

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

Note

يعلّم غربال إراتوستينس مضاعفات كل عدد أولي باستخدام الجمع (إضافة العدد الأولي مرارًا) أو الضرب (حساب مضاعفاته مباشرة)، بدلًا من فحص قابلية قسمة كل عدد.

لا تتحقق الاختبارات من أنك طبّقت الخوارزمية، بل من أنك توصلت إلى الأعداد الأولية الصحيحة فقط.

مثال

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

اكتب 2، 3، 4، 5، 6، 7، 8، 9، 10، واتركها كلها غير معلَّمة.
```
2 3 4 5 6 7 8 9 10
```
العدد 2 غير معلَّم، لذا فهو أولي. علّم 4 و6 و8 و10 بأنها «ليست أولية».
```
2 3 [4] 5 [6] 7 [8] 9 [10]
↑
```
العدد 3 غير معلَّم، لذا فهو أولي. علّم 6 و9 بأنها ليست أولية (تعلّم 6 اختياري، فهو معلَّم بالفعل).
```
2 3 [4] 5 [6] 7 [8] [9] [10]
  ↑
```
العدد 4 معلَّم بأنه «ليست أولية»، لذا نتجاوزه.
```
2 3 [4] 5 [6] 7 [8] [9] [10]
     ↑
```
العدد 5 غير معلَّم، لذا فهو أولي. علّم 10 بأنه ليست أولية (اختياري، فهو معلَّم بالفعل).
```
2 3 [4] 5 [6] 7 [8] [9] [10]
        ↑
```
العدد 6 معلَّم بأنه «ليست أولية»، لذا نتجاوزه.
```
2 3 [4] 5 [6] 7 [8] [9] [10]
           ↑
```
العدد 7 غير معلَّم، لذا فهو أولي.
```
2 3 [4] 5 [6] 7 [8] [9] [10]
              ↑
```
العدد 8 معلَّم بأنه «ليست أولية»، لذا نتجاوزه.
```
2 3 [4] 5 [6] 7 [8] [9] [10]
                 ↑
```
العدد 9 معلَّم بأنه «ليست أولية»، لذا نتجاوزه.
```
2 3 [4] 5 [6] 7 [8] [9] [10]
                     ↑
```
العدد 10 معلَّم بأنه «ليست أولية»، لذا نتوقف لأنه لم تعد هناك أعداد أخرى لفحصها.
```
2 3 [4] 5 [6] 7 [8] [9] [10]
                         ↑
```