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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى التنقل اذهب إلى البحث
غربال إراتوستينس
Sieve of Eratosthenes animation.gif
خطوات خوارزمية غربال إراتوستينس حتى العدد 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 in/2:
 if A[i] is true:


  for j = 2i, 3i, 4i, ..., while jn:
   A[j] = false
 
الآن كل الأعداد i حيث [A[i تساوي true هي أعداد أولية.

المتتاليات الحسابية[عدل]

غربال أويلر[عدل]

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

انظر أيضا[عدل]

مراجع[عدل]

  1. ^ "معلومات عن غربال إراتوستينس على موقع zthiztegia.elhuyar.eus"، zthiztegia.elhuyar.eus، مؤرشف من الأصل في 5 ديسمبر 2018.
  2. ^ "معلومات عن غربال إراتوستينس على موقع britannica.com"، britannica.com، مؤرشف من الأصل في 27 ديسمبر 2017.
  3. ^ "معلومات عن غربال إراتوستينس على موقع rosettacode.org"، rosettacode.org، مؤرشف من الأصل في 24 أبريل 2019.