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

[19 ان شاء الله]

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

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

وهذه صورة توضح عمل الخوارزمية
https://ar.wikipedia.org/w/index.php?...20111122163028

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