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

خوارزمية Sieve of Eratosthenes

602
2

تعتبر خوارزمية 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

(602)

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

Comment(2)

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

  2. السلام عليكم ورحمة الله وبركاته اخواني الااعزا ابائي العلماء اناالطالب عبدالرحمن عبدالملك محمد المعلمي من اليمن مجتهد في العلم ولديا العديد من الااكتشافات وقمت بإجاد العديدمن القوانين والنضريات في مجال الرياضيات والفيزيا والكيميا وعلم الفلك والسلوك الأنساني وعلم المحاسبه والأقتصاد والحمد الله اني قداستطعت وتوفقت في حل مسئلتين من احدا المسائل التي قام بعرضها المعهد الاامريكي وفرض مايون دولار لكل واحدة منها ثم انني قمت بئيجاد قاعده شامله عضمى لاايجاد جميع الااعداد الااوليه ولاكنني اخواني مهدور لااحد يسئل عني وكم مرات وسنين واناانشرذالك في كل المواقع ولاكن لاحياة لمن انادي وكم مرات اطلب من الدوله بئن تقوم بمساعدتي وتشجيعي واعطائي مااستحقه ولاكن لافائده وليس هناك من يستجيب فااناارجوكم غاية الرجا ان تساعدوني على نشرذالك وافائده العالم كله بشرط ان اكرم وان يتم اعطائي مااستحقه مقابل هذه الجهود العضيمه وان يتم مساعدتي في مواصلة التعليم ولكم مني جزيل الشكر والتقدير واني في انتضاركم عبر الاارقام التاليه 00967714715442 او 00967771350597 او على مواقعي في الفيس او جوجل وشكرآ

LEAVE YOUR COMMENT

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

مشاركة