كيف تتم معرفة الأعداد الأولية


أولا : غربال إيراتوستين (Sieve of Eratosthenes ):



كلمة غربال تعني طريقة للتصفية أو التنقية ، و تنسب هذه الطريقة للعالم الإغريقي إيراتوستين حيث اكتشفها ، و هي أسهل الطرق المستخدمة في الكشف عن الأعداد الأولية و يستطيع الطالب في المرحلة الإبتدائية العليا أو الإعدادية استخدامها ، و تزيد صعوبتها كلما كبرت الأعداد حتى تصبح غير فعالة مع الأعداد الكبيرة ، لذا تكون فعالة في الأعداد الصغيرة جدا ( الأقل من 1000000) .



و تقول هذه الطريقة أنه لإيجاد جميع الأعداد الأولية الأصغر من n اكتب في قائمة جميع هذه الأعداد الأصغر من n ثم استبعد جميع مضاعفات الأعداد الأولية بحيث تبدأ من مضاعفات 2 ثم 3 ثم 5 ثم 7 و هكذا فالأعداد المتبقية هي الأعداد الأولية و الجدول التالي يوضح مثال لغربال إيراتوستين المستخدم في الأعداد الأقل من 100 :

ثانيا : طريقة القسمة ( trial division ) :



تستخدم هذه الطريقة أيضا في الكشف عن الأعداد الأولية الصغيرة ، و هي أصعب من سابقتها ، و لكن باستطاعة طلاب المرحلة الثانوية إنجازها ، فلكي نفحص نعرف أن عددا ما n هل أولي ؟ فإننا نقسمه على جميع الأعداد الأولية الأقل من جذره التربيعي ، فعلى سبيل المثال لو أردنا أن نفحص أولية العدد 211 ، فإننا نحتاج لأن نقسمه على 2 ، 3 ، 5 ، 7 ، 11 ، 13 ، فإذا لم يقبل القسمة على أي منها فيكون العدد 211 أوليا و إلا فلا . و لا حاجة لنجرب قسمته على عدد أول أكثر من 13 لأن جذره التربيعي أقل من 15 ، و هذا يعني أن علينا أن نتوقف عن القسمة عندما نصل إلى جذره التربيعي التقريبي .



في الحقيقة قد تصبح هذه الطريقة صعبة عندما تكبر الأعداد فليس من السهل أن تستخدم الطريقة هذه بحذافيرها مع العدد 100000001 على سبيل المثال ، على الرغم أن هذا العدد لا يعتبر من الأعداد الكبيرة ، فلو جئنا إلى هذا العدد و أردنا أن نطبق طريقة القسمة عليه لمعرفة هل هو أولي أم لا ، فيجب علينا أن نبدأ مع الرقم 2 و نكرر ذلك حتى نصل إلى أحد قواسمه أو نتوقف عند العدد الأولي الأقل من جذره التربيعي مباشرة ، و إذا عرفنا أن sqrt(100000001)@ 10000 و عدد الأعداد الأولية الأقل من 10000 حسب صيغة ليجاندر و هي : p(n)=n/(log(n)-1.08366) هي :

p(10000)=10000/(log(10000)-1.08366) @ 3428 ، أي أنه علينا أن نقسم على 3428 عدد أولي تقريبا ، و لا يخفى أن في هذا صعوبة من حيث الوقت و الجهد ، لذلك استخدم الرياضيون و ابتكروا مهارات مختلفة و أدخلوا التحليل الرياضي فيها ، و لكن الحاسب الآلي سهل أمر هذه القسمة حيث كتبت برامج و خورازميات عديدة تنفذ القسمة آليا ، و باعتقادي أن من لديه معرفة بسيطة ببرنامج الإكسل الذي تصدره شركة مايكروسوفت ضمن مجموعة الأوفيس يستطيع اكتشاف أولية هذا الرقم باستخدام القسمة شريطة أن تكون لديه قائمة بكل الأعداد الأولية الأقل من 10000 و عددها بالدقة 1229 عددا .