خوارزمية بسيطة لمعرفة اذا ماكان العدد أوليا أم لا

[walid]

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

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

وهذه صورة توضح عمل الخوارزمية
http://ar.wikipedia.org/w/index.php?...20141122163028 (http://ar.wikipedia.org/w/index.php?title=%D9%85%D9%84%D9%81:Sieve_of_Eratos thenes_animation.gif&filetimestamp=20141122163028)

ملاحظة:
هل تعلم أن جميع الأعداد الأولية أحادها دائما ما يكون1أو 3 أو 7 أو 9 لأن جميع الأعداد التي تنتهي ب 0 أو 2 أو 4 أو 6 أو 8 هي من مضاعفات العدد 2 فليست بالتأكيد أولية، والأعداد التي تنتهي ب 5 هي من مضاعفات العدد 5 فليست أولية أيضاً.ولكن هذ لا يعني أن جميع الأعداد التي أحادها 1أو 3 أو 7 أو 9 أولية.



https://fbcdn-sphotos-d-a.akamaihd.net/hphotos-ak-ash4/482113_236967293114455_1193518507_n.png (http://www.dzbatna.com)
©المشاركات المنشورة تعبر عن وجهة نظر صاحبها فقط، ولا تُعبّر بأي شكل من الأشكال عن وجهة نظر إدارة المنتدى (http://www.dzbatna.com)©