اختبار الأولية حتى sqrt(n)

من المهارات الأساسية في الرياضيات تحديد ما إذا كان عدد واحد أوليًا. يمتلك العدد الأولي قاسمين بالضبط: الواحد ونفسه. لنختبر ذلك بسرعة. 🔍

يمكنك تجربة قسمة n على كل عدد من 2 حتى n ناقص 1. هذه الطريقة صحيحة، لكنها بطيئة بشكل مؤلم عندما تكون قيمة n كبيرة.

إليك الفكرة الأساسية: لا تحتاج إلى اختبار القواسم إلا حتى الجذر التربيعي لـ n. فلن يظهر أي عامل جديد بعد ذلك.

تأتي القواسم في أزواج حاصل ضربها يساوي n. ولو كان كلاهما أكبر من الجذر التربيعي، لتجاوز حاصل ضربهما قيمة n، وهذا مستحيل.

كرّر i من 2 ما دام حاصل ضرب i في نفسه لا يتجاوز n. يؤدي استخدام i*i إلى تجنّب أخطاء الفاصلة العائمة التي قد يسببها sqrt مع الأعداد الصحيحة الكبيرة.

الأعداد الأصغر من 2 ليست أولية أبدًا، لذا ارفضها مسبقًا. يحافظ هذا الفحص الوقائي على نظافة الحلقة الرئيسية وصحتها.

اجمع الخطوات معًا: افحص القيم الصغيرة، ثم افحص القواسم المحتملة حتى الجذر. وتعني أي قسمة دون باقٍ أن n مركب.

افحص العدد 2 بشكل منفصل، ثم اختبر الأعداد الفردية فقط. يؤدي تخطي الأعداد الزوجية إلى تقليل العمل إلى النصف تقريبًا دون أي تعقيد إضافي.

يعمل هذا الاختبار في زمن O(sqrt n). وبالنسبة إلى عدد واحد لا يتجاوز مليارًا، لا يتطلب ذلك سوى نحو 30,000 عملية بسيطة.

يتألق اختبار الجذر التربيعي عند التعامل مع استعلام واحد أو بضعة استعلامات. أما إذا احتجت إلى اختبار أولية نطاق كامل، فسيكون الغربال أسرع بكثير.

تجنّب المقارنة باستخدام i*i بدلًا من math.sqrt أخطاء التقريب التي قد تؤدي خطأً إلى قبول الأعداد الحدّية أو رفضها.

تأكّد من الحد الذي يجعل هذا الاختبار سريعًا.

يمكنك الآن اختبار أولية عدد واحد في زمن O(sqrt n)، وفحص القيم الصغيرة، وتخطي الأعداد الزوجية، واستخدام i*i للحفاظ على الدقة التامة. ✅