محقق الأعداد الأولية (مع التحليل إلى عوامل)

ما هو العدد الأولي

العدد الأولي عدد طبيعي أكبر من 1 ليس له قواسم موجبة غير 1 ونفسه. أوائل الأعداد الأولية: 2، 3، 5، 7، 11، 13، 17، 19، 23، 29، 31، 37. هي 'ذرات' حساب الأعداد الصحيحة — كل عدد صحيح ≥ 2 يمكن كتابته بشكل وحيد كحاصل ضرب أعداد أولية (نظرية الحساب الأساسية).

1 ليس أولياً باتفاق. 0 والأعداد السالبة ليست أولية. 2 هو العدد الزوجي الأولي الوحيد — كل عدد زوجي آخر يقبل القسمة على 2 فهو مركّب.

كيف يعمل الاختبار

نستخدم قسمة تجريبية: نختبر القابلية للقسمة على 2، ثم 3، ثم 5، 7، 11، … حتى √n. إن لم يقسم أي منها بشكل نظيف، فـ n أولي. نستخدم تحسين 6k±1 الذي يختبر فقط المرشحين بالشكل 6k+1 أو 6k−1 (لأن جميع الأعداد الأولية > 3 بهذا الشكل)، مما يقلل عدد الاختبارات بثلثين.

القسمة التجريبية سريعة لـ n حتى ~10^15 (أقل من ثانية). فيما وراء ذلك، تُحتاج اختبارات متقدمة كـ Miller-Rabin (احتمالية) أو AKS (حتمية). نضع حداً عند 10^18 لمنع تجميد المتصفح على مدخلات قصوى.

لماذا تهم الأعداد الأولية

التشفير: تشفير RSA يضرب عددين أوليين من ~1000 رقم لإنتاج عدد يصعب تحليله. الأمان يعتمد على صعوبة تحليل الأعداد الكبيرة — تحدٍّ يُدرَس منذ آلاف السنين.

التعليم الرياضي: التحليل لعوامل أولية أساسي. مفاهيم كـ GCD وLCM والحساب المعياري والكسور ونظرية الأعداد تُبنى جميعها على هيكل العوامل الأولية.

علوم الحاسوب: أحجام جداول التجزئة ومولدات الأرقام العشوائية وكثير من الخوارزميات تستخدم الأعداد الأولية لخصائص قابلية القسمة المميزة لها.