🎛️ شاهد الغربال يقوم بعمله خطوة بخطوة
انقر على «الخطوة التالية» لشطب مضاعفات 2، ثم 3، ثم 5، وهكذا. الناجون هم الأعداد الأولية.
العدد الأولي الحالي
2
الأعداد الأولية المكتشفة
0
التعقيد الإجمالي
O(N log log N)
نبحث عن الأعداد الأولية حتى 120. سنشطب مضاعفات 2، ثم 3، ثم 5، وهكذا.
🪜 إراتوستينس: سيد القياس
إراتوستينس القوريني (276-194 قبل الميلاد) عالم يوناني، وثالث أمين مكتبة الإسكندرية. اشتهر بقياسه محيط الأرض بخطأ لا يتجاوز 2% فقط باستعمال ظل بئر في أسوان ومسلّة في الإسكندرية.
من بين أعماله الرياضية: خوارزمية لإيجاد الأعداد الأولية، تُسمى اليوم غربال إراتوستينس. هذه الخوارزمية فعّالة لدرجة أنها لا تزال تُدرَّس في جميع دروس الخوارزميات وتُستعمل عمليًا في الحسابات التشفيرية اليومية.
🎯 الخوارزمية: حذف منهجي
الفكرة المركزية: لإيجاد جميع الأعداد الأولية ≤ N، نتقدّم عبر الحذف. نبدأ بكتابة جميع الأعداد الصحيحة من 2 إلى N. ثم نشطب مضاعفاتها بشكل منهجي.
خوارزمية غربال إراتوستينس
- اكتب جميع الأعداد الصحيحة من 2 إلى N.
- أول عدد غير مشطوب هو 2. إنه عدد أولي. اشطب جميع مضاعفاته (4، 6، 8، ...).
- العدد التالي غير المشطوب هو 3. إنه عدد أولي. اشطب جميع مضاعفاته (9، 15، 21، ...).
- التالي غير المشطوب هو 5. إنه عدد أولي. اشطب 25، 35، ...
- تابع إلى أن يصير العدد الأولي الحالي > √N.
- جميع الأعداد غير المشطوبة المتبقية أعداد أولية.
⚡ لماذا نتوقف عند √N؟
حيلة أساسية: إذا كان لـ N قاسم d > √N، فإن N/d < √N هو أيضًا قاسم. إذن لـ N حتمًا قاسم ≤ √N (إذا لم يكن أوليًا). وهذا القاسم ≤ √N هو نفسه جداء أعداد أولية ≤ √N. إذن جميع مضاعفات الأعداد الأولية > √N قد شُطبت مسبقًا بواسطة الأعداد الأولية ≤ √N.
النتيجة: لغربلة حتى N = 100، يكفي شطب مضاعفات 2، 3، 5، 7 (الأعداد الأولية ≤ √100 = 10). من أجل N = 10 000، تكفي الأعداد الأولية ≤ 100. من أجل N = 10⁹، تكفي الأعداد الأولية ≤ √10⁹ ≈ 31 623.
🚀 التعقيد: O(N log log N)
كم عملية ينفّذ الغربال؟ نَعُدّ عدد المرات التي نشطب فيها عددًا. من أجل كل عدد أولي p ≤ √N، نشطب N/p من المضاعفات. العدد الإجمالي للعمليات هو:
∑p premier ≤ N N/p ~ N · ln(ln N)
هذا المجموع معروف منذ ميرتنس (1874). من أجل N = 10⁹، يعطي ≈ 10⁹ · ln(ln 10⁹) ≈ 3.5 مليار عملية. قابل للإنجاز في بضع ثوانٍ على حاسوب حديث.
📐 تنفيذ حديث (Python / C++)
إليك الخوارزمية بلغة Python:
def crible(N):
sieve = [True] * (N + 1)
sieve[0] = sieve[1] = False
for i in range(2, int(N**0.5) + 1):
if sieve[i]:
for j in range(i*i, N + 1, i):
sieve[j] = False
return [i for i, v in enumerate(sieve) if v]7 أسطر. من أجل N = 10⁶، يعطي جميع الأعداد الأولية ≤ 1 000 000 في حوالي 0.1 ثانية. الخوارزمية بسيطة لدرجة أنها غالبًا أول خوارزمية «غير تافهة» تُتعلَّم في دروس البرمجة.
🎯 تحسينات حديثة
- تجاهل الأعداد الزوجية: نعالج 2 على حدة، ولا نخزّن سوى الأعداد الفردية. يوفّر عاملًا قدره 2 في الذاكرة والوقت.
- عجلة الأعداد الأولية: نتجاوز مضاعفات 2، 3، 5، إلخ باستعمال عجلات. يوفّر عاملًا قدره ~3.
- الغربال المُجزّأ: نقسّم N إلى كتل تسع في ذاكرة المخبئ للمعالج. يوفّر عاملًا قدره 5-10 على القيم الكبيرة جدًا لـ N.
- غربال أتكين (2003): غربال متقدّم بتعقيد O(N / log log N)، لكنه أكثر تعقيدًا.
- الغربال المتوازي: نوزّع الأجزاء على عدة أنوية للمعالج.
🔬 متى يكفّ الغربال عن كونه عمليًا؟
من أجل القيم الكبيرة جدًا لـ N (≥ 10¹²)، يصبح الغربال الكلاسيكي غير عملي لأنه يجب حجز جدول من N قيمة بوليانية — وهو ما لم يعد يسع في الذاكرة. عند هذا المقياس، نستعمل:
- الغربال المُجزّأ: نفحص N بشرائح من 10⁶ إلى 10⁸ تسع في الذاكرة.
- اختبارات الأولية الاحتمالية (ميلر-رابين، AKS): لم نعد نغربل، بل نختبر عددًا واحدًا في كل مرة.
- فهارس محسوبة مسبقًا: الأعداد الأولية ≤ 10¹² مجدولة سلفًا ومتاحة للعموم.
🌍 التطبيقات: لماذا نحتاج إليه
- التشفير RSA: توليد أعداد أولية من 1024 إلى 4096 بت. يُستعمل الغربال لحذف القواسم الصغيرة بسرعة قبل اختبار أكثر كلفة.
- التجزئة وجداول التجزئة: نبحث عن أعداد أولية قريبة من حجم مستهدف لتفادي التصادمات.
- نظرية الأعداد: اختبار التخمينات (غولدباخ، ريمان، الأعداد الأولية التوأم...) يتطلب معرفة الأعداد الأولية حتى عتبة مرتفعة.
- مسابقات البرمجة: إراتوستينس من أكثر الخوارزميات استعمالًا في المسابقات (أولمبياد المعلوميات، Code Jam، ICPC).
📐 الرابط مع برنامجك
الغربال في متناول البكالوريا علوم رياضية بالكامل:
- الأعداد الأولية (برنامج الحسابيات الثانية بكالوريا علوم رياضية): التعريف، الخاصيات.
- القواسم والمضاعفات: يعتمد الغربال على هذه المفاهيم الأساسية.
- الخوارزميات (ما بعد البكالوريا، TIPE): تمرين ممتاز في الحلقات المتداخلة.
- التعقيد: عَدّ عدد العمليات تمرين نموذجي.
- المجاميع التوافقية: يستعمل برهان التعقيد ∑ 1/p، الذي يربط بمتسلسلات برنامج التحليل.
🎯 طُرفة صغيرة: جدول كورتيس (1772)
في عام 1772، نشر جوزيف كورتيس يدويًا جدولًا بجميع الأعداد الأولية ≤ 100 000، محسوبة بغربال إراتوستينس. هذا الجدول، الذي استغرق سنوات لتجميعه، يحتوي على 9 592 عددًا أوليًا.
اليوم، يولّد برنامج Python نفس الجدول في 0.01 ثانية. مقارنة بين العصور: 100 سنة من العمل اليدوي ⇔ 10 ميلي ثانية للحاسوب. الخوارزمية بقيت كما هي، فقط الحساب هو الذي تغيّر.
Vérifie ta compréhension
3 questions courtes pour valider tes acquis. Tu peux réessayer.