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

غربال إراتوستينس
خطوات خوارزمية غربال إراتوستينس حتى العدد 120.
بيانات عامّة
الصنف
سمي نسبة لـ

تعديل - تعديل مصدري - تعديل ويكي بياناتحول القالب

غربال إراتوستينس هي خوارزمية بسيطة لإيجاد جميع الأعداد الأولية حتى عدد ما.[1][2][3] تعمل هذه الخوارزمية بكفاءة من أجل الأعداد الأولية الصغيرة (حتى عشرة ملايين). صممت هذه الخوارزمية من قبل إراتوستينس الرياضياتي الإغريقي.

وصف الخوارزمية

[عدل]

لإيجاد الأعداد الأولية الأصغر من n تتبع الخوارزمية الخطوات التالية:

  1. أنشئ قائمة بجميع الأعداد من الرقم 2 إلى العدد الذي تريد,
  2. نبدأ بقيمة ل p تساوي 2، أول الأعداد الأولية,
  3. اشطب من القائمة جميع الأعداد من مضاعفات p والتي هي أكبر من p,
  4. ابحث عن العدد التالي غير المشطوب في القائمة، هذا العدد هو العدد الأولي التالي، وسيكون هو العدد p التالي,
  5. كرر الخطوات 3 و4 حتى يصير p2 هي أكبر من n,
  6. جميع الأعداد الباقية على القائمة هي أعداد أولية.

مثال

[عدل]

تعقيد الخوارزمية

[عدل]

البرمجة

[عدل]
المدخل: عدد n طبيعي أكبر قطعا من 1



 
ليكن A جدولا من القيم البوليانية، مفهرسا بالأعداد الطبيعية من 
2 حتى n، كلها تساوي في البداية ل true.



 
for i = 2, 3, 4, ...

, while i ≤ n/2:
 if A[i] is true:



  for j = 2i, 3i, 4i, ..., while j ≤ n:
   A[j] = false
 

الآن كل الأعداد i حيث [A[i تساوي true هي أعداد أولية.

المتتاليات الحسابية

[عدل]

غربال أويلر

[عدل]

انظر برهان صيغة جداء أويلر بالنسبة لدالة زيتا لريمان.

انظر أيضا

[عدل]

مراجع

[عدل]
  1. ^ "معلومات عن غربال إراتوستينس على موقع zthiztegia.elhuyar.eus". zthiztegia.elhuyar.eus. مؤرشف من الأصل في 2018-12-05.
  2. ^ "معلومات عن غربال إراتوستينس على موقع britannica.com". britannica.com. مؤرشف من الأصل في 2017-12-27.
  3. ^ "معلومات عن غربال إراتوستينس على موقع rosettacode.org". rosettacode.org. مؤرشف من الأصل في 2019-04-24.
أيقونة بذرة

هذه بذرة مقالة بحاجة للتوسيع. فضلًا شارك في تحريرها.