عن غربال إراتوستينس - أقدم غربال للأعداد الأولية
يجد غربال إراتوستينس كل الأعداد الأولية حتى حد معين دون أي عملية قسمة. عليك فقط أن تعدّ: اشطب كل عدد ثانٍ بعد 2، وكل عدد ثالث بعد 3، وهكذا. ما يتبقى هو الأعداد الأولية. بعد أكثر من ألفي عام، لا يزال من أسرع الطرق لسردها.
إراتوستينس القوريني
عاش إراتوستينس تقريبًا من 276 إلى 194 قبل الميلاد، وتولى رئاسة مكتبة الإسكندرية الكبرى. اشتهر أكثر ما اشتهر بقياس حجم الأرض من أطوال الظلال في مدينتين. سُمي الغربال باسمه لأن نيقوماخوس الجرشي وصفه بأنه طريقته في كتاب مدخل إلى علم الحساب، الذي كُتب نحو عام 100 للميلاد.
كيف يعمل الغربال
اكتب الأعداد من 2 إلى N. العدد الأول، 2، أولي: اشطب 4 و6 و8 وكل مضاعفات 2 الأخرى. العدد التالي المتبقي، 3، أولي: اشطب 9 و12 و15 وهكذا. تابع مع 5 و7 والأعداد المتبقية التالية. العدد الذي لا يُشطب أبدًا ليس له عامل أصغر، فهو أولي.
التوقف عند الجذر التربيعي
لكل عدد مركب حتى N عامل أولي لا يزيد على الجذر التربيعي لـ N. لذلك بمجرد أن يتجاوز p² العدد N، لا يبقى شيء للشطب. للأعداد الأولية حتى 100 تحتاج فقط إلى 2 و3 و5 و7، وحتى 1000 تحتاج إلى الأعداد الأولية حتى 31.
ما مدى سرعته؟
يحتاج الغربال إلى نحو N log log N خطوة، وهذا ينمو أسرع قليلًا فقط من N نفسه. لا تزال الحواسيب تستخدمه، غالبًا على أجزاء كغربال مجزأ، لسرد الأعداد الأولية حتى المليارات. أما لاختبار ما إذا كان عدد كبير واحد أوليًا، فهناك طرق أخرى أسرع.
الأسئلة المتداولة
من اخترع غربال إراتوستينس؟
سُمي باسم إراتوستينس القوريني، العالم اليوناني من القرن الثالث قبل الميلاد. أقدم وصف مكتوب له يعود إلى نيقوماخوس الجرشي نحو عام 100 للميلاد.
لماذا يبدأ الغربال الشطب من p²؟
لكل مضاعف أصغر لـ p عامل أولي أصغر، لذا فقد شطبه عدد أولي أصغر بالفعل.
كم عددًا أوليًا يوجد تحت 1000؟
يوجد 168 عددًا أوليًا تحت 1000. أكبرها 997.
الأدوات ذات الصلة
غربال إراتوستينس
شاهد غربال إراتوستينس وهو يجد الأعداد الأولية حتى 100 أو 200 أو 500 أو 1000. يشطب كل عدد أولي مضاعفاته بلونه الخاص، خطوة بخطوة.
حلزون أولام
ارسم حلزون أولام في متصفحك. علِّم الأعداد الأولية، واقرأ كثير الحدود التربيعي على كل قطر، وافتح سلسلة أويلر المتصلة من 40 عددًا أوليًا.
حلزون أولام
كيف يضع حلزون ستانيسواف أولام لعام 1963 الأعداد الصحيحة على شبكة مربعة، ولماذا تتجمع الأعداد الأولية على أقطار تربيعية، وأين تقع أعداد أويلر الأولية الأربعون حين يبدأ الحلزون من 41.
حدسية كولاتز
استكشف مسألة كولاتز 3n+1 في متصفحك. تتبّع متتاليات البَرَد، ونمِّ شجرة كولاتز هندسية، وكبّر كسيرية كولاتز المتصلة.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
جرّب غربال إراتوستينس