قائمة الأعداد الأولية وأداة التحقق
اعرض جميع الأعداد الأولية ضمن نطاق معيّن (غربال إراتوستينس)، أو تحقق مما إذا كان عدد واحد أوليًا — نتائج فورية.
1,057 مشاهدة
النطاق كبير جدًا — أدخل 1,000,000 كحد أقصى.
0 عدد الأعداد الأولية الموجودة
كيف تعمل الأداة
تنتقل الأداة بين خوارزميتين مختلفتين، كل منهما تناسب سؤالًا مختلفًا. يجد وضع القائمة كل الأعداد الأولية حتى حد معيّن باستخدام غربال إراتوستينس، وهو من أقدم الخوارزميات التي لا تزال تُستخدم يوميًا (يُنسَب إلى عالم الرياضيات اليوناني إراتوستينس، القرن الثالث قبل الميلاد). بدءًا من 2، يشطب كل مضاعفات 2 باعتبارها مركّبة، ثم ينتقل إلى أول رقم غير مشطوب (3) ويشطب مضاعفاته، ثم إلى الرقم غير المشطوب التالي (5)، وهكذا. وكل ما يبقى دون شطب عند بلوغ الجذر التربيعي للحد يكون عددًا أوليًا. مثال بسيط: لغربلة الأعداد حتى 30، اشطب مضاعفات 2 (4، 6، 8، …)، ثم مضاعفات 3 (6، 9، 12، … بعضها مشطوب مسبقًا)، ثم مضاعفات 5 (10، 15، …) — وبما أن 5×5=25 ≤ 30 لكن 7×7=49 > 30، يمكنك التوقف هنا؛ وما يتبقى — 2، 3، 5، 7، 11، 13، 17، 19، 23، 29 — هو القائمة الكاملة. يعمل هذا في زمن O(n log log n)، أي يبقى سريعًا حتى وإن اتسع النطاق إلى مئات الآلاف.
يجيب وضع التحقق عن سؤال مختلف — هل هذا العدد المحدد أولي؟ — باستخدام القسمة التجريبية حتى الجذر التربيعي. لاختبار ما إذا كان n أوليًا، يكفي التحقق من القواسم من 2 حتى √n. والمنطق وراء ذلك: لو كان n = a × b وكان كل من a و b أكبر من √n، لكان حاصل ضربهما أكبر من n، وهذا مستحيل. إذن لا بد أن يكون أحد العاملين على الأقل مساويًا لـ√n أو أصغر منه، وسيُعثَر عليه قبل انتهاء الحلقة. مثال: للتحقق من العدد 97، يكفي اختبار القسمة على 2 و3 و5 و7 فقط (لأن 9²=81 ≤ 97 بينما 10²=100 > 97) — لا يقسمه أي منها تمامًا، إذن 97 عدد أولي.
ما ينبغي أن تعرفه
يوجد الوضعان لأنهما يقدّمان مفاضلة مختلفة: الغربال فعّال في إنتاج أعداد أولية كثيرة دفعة واحدة، لكنه يُهدر الذاكرة والوقت إن كنت تهتم بعدد واحد فقط قرب حد هائل؛ أما القسمة التجريبية فهي فعّالة لتحقق واحد، لكنها بطيئة جدًا إن كُرِّرت لكل عدد في نطاق كبير واحدًا تلو الآخر. اختيار الوضع المناسب للمهمة هو بالضبط سبب توفير هذه الأداة للوضعين معًا.
- يُستبعَد 1 من الأعداد الأولية بحكم التعريف والعُرف — إذ له قاسم واحد فقط لا اثنان، وهو ما كان سيُخلّ بتفرّد التحليل إلى العوامل الأولية لو سُمِح بإدراجه.
- 2 هو العدد الأولي الزوجي الوحيد؛ فكل عدد زوجي آخر يقبل القسمة على 2 ولذلك يكون مركّبًا.
- مع تزايد الأعداد، تُصبح الأعداد الأولية أندر في المتوسط، لكنها لا تتوقف عن الظهور أبدًا — فقد أثبت إقليدس قبل أكثر من ألفي عام أن عددها لا نهائي.
الأسئلة الشائعة
ما الذي يُعدّ عددًا أوليًا؟
هو عدد طبيعي أكبر من 1 وله قاسمان موجبان فقط: 1 ونفسه. العدد 1 ليس أوليًا لأن له قاسمًا واحدًا فقط، ولا تُعدّ الأعداد السالبة أولية أو مركّبة على الإطلاق.
ما أكبر نطاق يمكنني عرض أعداده؟
حتى 1,000,000 — يبقى غربال إراتوستينس سريعًا ضمن هذا النطاق (تعقيده O(n log log n) ينمو ببطء شديد) ويبقى متصفحك سريع الاستجابة.
لماذا تكتفي القسمة التجريبية بالتحقق حتى الجذر التربيعي؟
إذا كان للعدد n قاسم أكبر من √n، فلا بد أن يقترن بقاسم أصغر من √n (لأن حاصل ضربهما يساوي n). إذن يملك أي زوج من العوامل عضوًا واحدًا على الأقل عند الجذر التربيعي أو أقل منه — والتحقق أبعد من ذلك زائد عن الحاجة.
لماذا لا تُستخدم القسمة التجريبية للعرض أيضًا؟
يمكن ذلك، لكنه سيكون أبطأ بكثير: اختبار كل عدد في النطاق على حدة حتى جذره التربيعي الخاص به يتطلب عملًا متكررًا أكبر بكثير مما يفعله الغربال، الذي يحذف مضاعفات كل عدد أولي في مرور واحد فعّال عبر النطاق بأكمله.
هل الأعداد الأولية لا نهائية العدد؟
نعم — قدّم إقليدس برهانًا على ذلك نحو عام 300 قبل الميلاد: افترض وجود قائمة منتهية بكل الأعداد الأولية، اضرِبها معًا وأضف 1؛ الناتج لا يقبل القسمة على أي عدد أولي في القائمة، فإما أن يكون هو نفسه عددًا أوليًا جديدًا أو يملك عاملًا أوليًا غير موجود في القائمة. وفي الحالتين، تكون القائمة ناقصة.
أدوات مشابهة
الإبلاغ عن مشكلة
قائمة الأعداد الأولية وأداة التحقق
التعليقات
لا توجد تعليقات بعد — كن أول من يكتب تعليقًا!