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

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

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

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

1. أنشئ قائمة بجميع الأعداد من الرقم 2 إلى العدد الذي تريد,
2. نبدأ بقيمة ل p تساوي 2، أول الأعداد الأولية,
3. اشطب من القائمة جميع الأعداد من مضاعفات p والتي هي أكبر من p,
4. ابحث عن العدد التالي غير المشطوب في القائمة، هذا العدد هو العدد الأولي التالي، وسيكون هو العدد p التالي,
5. كرر الخطوات 3 و4 حتى يصير p² هي أكبر من 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 هي أعداد أولية.

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

غربال أويلر

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

مقالات ذات صلة

• غربال أتكين,

مراجع

وصلات خارجية

• Eratosthenes, sieve of at Encyclopaedia of Mathematics
• Interactive JavaScript Page
• Sieve of Eratosthenes by George Beck, Wolfram Demonstrations Project.
• Sieve of Eratosthenes in Haskell
• Sieve of Eratosthenes algorithm illustrated and explained. Java and C++ implementations.
• A related sieve written in x86 assembly language
• A highly optimized Sieve of Eratosthenes in C
• A parallel implementation in C#
• SieveOfEratosthenesInManyProgrammingLanguages c2 wiki page
• The Art of Prime Sieving Sieve of Eratosthenes in C from 1998 with nice features and algorithmic tricks explained.

موسوعات ذات صلة :

• موسوعة خوارزميات
• موسوعة علم الحاسوب
• موسوعة نظرية الأعداد