Home خوارزميات خوارزمية Sieve of Eratosthenes
خوارزمية Sieve of Eratosthenes

خوارزمية Sieve of Eratosthenes

513
1

تعتبر خوارزمية Sieve of Eratosthenes من أسهل الخوارزميات لإيجاد الأعداد الأولية Prime Numbers ضمن مجال معين من الأعداد الصحيحة n ، حيث تقوم فكرتها على حذف مضاعفات الأعداد داخل هذا المجال ، حيث أن تعريف الأعداد الأولية يستبعد وجود الأعداد التي يمكن إيجادها كحاصل ضرب عددين.

الخوارزمية من wikipedia

1. Create a list of consecutive integers from two to n: (2, 3, 4, …, n).
2. Initially, let p equal 2, the first prime number.
3. Strike from the list all multiples of p greater than p.
4. Find the first number remaining on the list greater than p (this number is the next prime); let p equal this number.
5. Repeat steps 3 and 4 until p^2 is greater than n.
6. All the remaining numbers on the list are prime.

سنوضح الخوارزمية عبر مثال بسيط لإيجاد الأعداد الأولية من 1 إلى 100.
(ملاحظة: العدد 1 لا يعتبر عدد أولي حيث أنه لا يوجد عددين مختلفين يقسما العدد 1) :

في البداية سننشئ مصفوفة من الأعداد :

eratosthenes-ex-0

سنبدأ من العدد الأولي 2 ، وسنقوم بإزالة كل مضاعفاته ابتداءا من 4 :

eratosthenes-ex-1

ملاحظة: اللون الاخضر يعني عدد أولي ، أما الأحمر فهو ليس أولي.

العدد 3 هو أولي ، وسنحذف كل مضاعفاته ابتداءا من 9 :

eratosthenes-ex-2

نفس الفكرة مع العدد 5 :

eratosthenes-ex-3

وكذلك العدد 7:

eratosthenes-ex-4

العدد التالي الآن هو 11 ، لكن سنتوقف هنا لأن مربع العدد 11 أكبر من المجال المطلوب 100.

eratosthenes-ex-5

إذاً الأعداد الأولية من 1 إلى 100 هي :

eratosthenes-ex-6

مثال آخر :

Animation_Sieve_of_Eratosth-2-ca
الصورة متحركه قم بالضغط عليها لمشاهدتها

تطبيق الخوارزمية :

هذا تطبيق بسيط للخوارزمية باستخدام سي++ ، والفكرة مشابهة تماما للمثال في الأعلى حيث سأنشئ مصفوفة من 100 عنصر ، وسأضع جميع القيم فيها مساوية للواحد دلالة على أن كل العناصر هي أولية ، وبعدها عندما نجد عدد مركب Composite number وليكن i سنجعل قيمة العنصر i هي الصفر دلالة على أنه تم حذف العنصر.

شرح بسيط :

هنا تم انشاء المصفوفة وتعيين القيمة 1 لكل الأعداد دلالة على أنها أولية ، أما العدد 1 فتم تعيين القيمة 0 له دلالة على أنه ليس عدد أولي.

لا يوجد داعي لأن نمر على جميع الأعداد من 1 الى 100 ! سنبدأ من العدد 2 لأن العدد 1 قد ذكرنا بأنه ليس أولي ، وسننتهي عند العدد 10 (تأتي من تطبيق الجذر التربيعي على n) لأنه عنما تعمل الخوارزمية على العدد 2 و 3 و 5 و 7 و9 ستجد أننا قد مررنا على كل الأعداد (المضاعفة) في هذا المجال.

في البداية سيتم اختبار هل العدد ليس أولي ؟ إذا كانت الاجابة لا فهذا يعني أن العدد أولي ويجب معرفة مضاعفاته لكي نقوم بازالتها .
أما إذا كانت الإجابة نعم فهذا يعني أن هذا العدد مضاعف Composite number وبالتأكيد مضاعفات هذا العدد هي ليس أولية وقد تم ازالتها من قبل.

نتيجة البرنامج :
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

وهذا تطبيق آخر للدالة :

مصادر:
Wikipedia
Prime_number
Sieve_of_Eratosthenes
كتاب Algorithms in C.

الكود بالمرفقات.
printprime.cpp.tar

(513)

أحمد عصام مهندس برمجيات مهتم بعلوم الحاسب ، وكل ما يتعلق ب Qt و KDE.

Comment(1)

  1. التعريف غير دقيق “ضمن مجال معين من الأعداد الصحيحة n”
    ربما “ضمن سلسلة (أو مجال) الأعداد الصحيحة من 2 وحتى n” أوضح وأدق 🙂

LEAVE YOUR COMMENT

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *

مشاركة