Check Prime Number
العدد الأولي هو عدد صحيح أكبر من 1 لا يقبل القسمة إلا على 1 وعلى نفسه. يُعطى لك عدد صحيح موجب n. أرجِع true إذا كان n أوليًا، وfalse خلاف ذلك. العدد 1 ليس أوليًا.
الدالة
- ninteger
- العدد الصحيح الموجب المراد اختباره
- تُرجعboolean
- صحيح إذا كان n عددًا أوليًا، وخطأ بخلاف ذلك
القيود
1 ≤ n ≤ 231 - 1
أمثلة
- المدخلات
- n = 29
- المخرجات
- true
- الشرح
- لا يقسم أيٌّ من
2أو3أو4أو5العدد29، و6 × 6 = 36يتجاوز29بالفعل، لذا لا يتبقى أي قاسم للعثور عليه.29عدد أولي.
- المدخلات
- n = 1
- المخرجات
- false
- الشرح
- العدد الأولي له قاسمان بالضبط،
1ونفسه. أما1فله قاسم واحد فقط، لذا فالإجابة هيfalse.
- المدخلات
- n = 91
- المخرجات
- false
- الشرح
- يبدو
91عددًا أوليًا، لكن7 × 13 = 91. يظهر القاسم7قبل أن يتجاوز البحث√91 ≈ 9.5.
+15 اختبارات مخفية عند الإرسال
سؤال إضافي
كل عدد أولي أكبر من 3 يكون على الصورة 6k-1 أو 6k+1. هل يمكنك الاستفادة من ذلك لاختبار ثلث القواسم المرشحة فقط؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
العدد الأولي ليس له أي قاسم بين
2وn-1. هل تحتاج حقًا إلى اختبار هذا النطاق بأكمله؟إذا كان
dيقسمn، فإنn / dيقسمه أيضًا، ويكون أحدهما على الأكثر√n. يمكنك التوقف عندما يتجاوزd * dn.استبعد أولًا
n < 2والأعداد الزوجية غير2. ثم اختبر القواسم الفردية بدءًا من3ما دامd * d ≤ n، مع إبقاءd * dفي نوع ذي 64 بت.
الحل
ينصّ التعريف على استبعاد كل قاسم من 2 إلى n-1، وهذا يعني إجراء أكثر من ملياري عملية قسمة عند أكبر قيمة أولية للمدخلات. تأتي القواسم في أزواج حاصل ضربها n، ويكون الأصغر في كل زوج أقل من أو يساوي √n. لذا لا تبحث إلا حتى √n، أي نحو 23,000 مرشحًا فرديًا على الأكثر.
جرّب كل قاسم
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
يعطيك التعريف الخوارزمية. يكون العدد n ≥ 2 أوليًا عندما لا يقسمه أي عدد من 2, 3, ..., n-1. اختبر كل قيمة مرشحة d باستخدام n % d == 0 وأعِد false عند أول قيمة تقسمه. بالنسبة إلى 91، تجرّب الحلقة الأعداد من 2 إلى 6 وتتوقف عند 7.
تعامل مع n < 2 أولًا. عند n = 1، يكون نطاق القيم المرشحة فارغًا، لذا لن تعثر الحلقة مطلقًا على قاسم، وستعتبر 1 عددًا أوليًا.
تتوقف الأعداد المركبة عادةً مبكرًا، لكن العدد الأولي يجتاز كل اختبار، لذا تستمر الحلقة حتى النهاية. بالنسبة إلى n = 2147483647، وهو عدد أولي، يعني ذلك إجراء نحو 2.1 × 10^9 عملية قسمة، وهو عدد يفوق بكثير ما يمكن إنجازه في بضع ثوانٍ.
الخوارزمية
- إذا كان
n < 2، فأعِدfalse. - كرّر
dمن2إلىn-1. - إذا كان
n % d == 0، فأعِدfalse. - بعد الحلقة، أعِد
true.
def isPrime(n):
if n < 2:
return False
for d in range(2, n):
if n % d == 0:
return False
return Trueالقسمة التجريبية حتى الجذر التربيعي
الفكرة
تأتي القواسم في أزواج. إذا كان d يقسم n، فإن n / d يقسمه أيضًا، وحاصل ضربهما يساوي n. لا يمكن أن يكون كلاهما أكبر من √n، لأن حاصل ضربهما عندئذ سيكون أكبر من n. لذا، إذا كان لـ n أي قاسم غير 1 ونفسه، فله قاسم لا يتجاوز √n. بالنسبة إلى 91، الزوج هو 7 و13، و7 ≤ 9.5. إذا لم يقسم n أي عدد حتى √n، فلن يقسمه أي عدد أكبر منه أيضًا.
اكتب الحد على صورة d * d ≤ n بدلًا من استدعاء دالة الجذر التربيعي. هكذا تبقى ضمن الأعداد الصحيحة، من دون تقريب. علامة المساواة مهمة: 49 = 7 × 7، وقاسمه 7 يقع تمامًا عند √49.
يمكنك أيضًا تخطي نصف المرشحين. عالج 2 بمفرده: لا يكون n الزوجي أوليًا إلا إذا كان 2. بعد ذلك، لا يكون لـ n الفردي سوى قواسم فردية، لذا ابدأ من 3 وتقدّم بمقدار 2. بالنسبة إلى n = 2147483647، ستُنفَّذ الحلقة الآن نحو 23,000 مرة بدلًا من 2.1 × 10^9.
الخوارزمية
- إذا كان
n < 2، فأعدfalse. - إذا كان
nزوجيًا، فأعد ما إذا كانn == 2. - ابدأ
dعند3وكرّر ما دامd * d ≤ n، مستخدمًا نوعًا بعرض 64 بت لـd. - إذا كان
n % d == 0، فأعدfalse. وإلا فأضف2إلىd. - بعد انتهاء الحلقة، أعد
true.
def isPrime(n):
if n < 2:
return False
if n % 2 == 0:
return n == 2 # 2 is the only even prime
d = 3
while d * d <= n:
if n % d == 0:
return False
d += 2
return True
أخطاء شائعة وحالات حدّية
يمكن تلخيص الفكرة في سطر واحد. تكمن الأخطاء عند الحدود: أصغر المدخلات وآخر قاسم.
- إرجاع
trueللقيمة1. لها قاسم واحد، لا قاسمان، لذا فهي ليست عددًا أوليًا. - رفض
2لأنها زوجية. تحقّق منn == 2قبل استبعاد الأعداد الزوجية. - تكرار الحلقة ما دام
d * d < nبدلًا من≤. عندئذٍ تُقبل مربعات الأعداد الأولية مثل9و49و2147117569 = 46337²على أنها أعداد أولية. - حدوث تجاوز في
d * d. فيintذي 32 بت، لا تتسع القيمة46341 × 46341 = 2147488281، فتلتف إلى عدد سالب، ولذلك يظل الاختبار ناجحًا وتستمر الحلقة إلى ما بعد√nبكثير. استخدم نوعًا ذا 64 بت للقيمةd، أو قارنd ≤ n / dبدلًا من ذلك. - أخذ الحد من
sqrtذي الفاصلة العائمة ثم اقتطاعه. تكون قيمةdoubleدقيقة لكل قيمةnهنا، لكن مع مدخلات 64 بت، قد يؤدي التقريب إلى قيمة أقل بواحد من الجذر الحقيقي، فتُتخطى قيمة القاسم الوحيدة المهمة. لا ينطويd * d ≤ nعلى هذا الخطر.
أسئلة شائعة4
ما هو التعقيد الزمني للتحقق مما إذا كان العدد أوليًا؟
يستغرق اختبار القسمة حتى √n زمنًا قدره O(√n) ومساحة قدرها O(1). بالنسبة إلى n حتى 2^31-1، فهذا يعني ما لا يزيد على نحو 46,000 عملية قسمة، أو 23,000 عند تخطي القواسم الزوجية. اختبار كل قاسم حتى n-1 يتطلب زمنًا قدره O(n)، أي نحو ملياري خطوة لأكبر قيمة إدخال.
لماذا تتحقق من القواسم حتى الجذر التربيعي لـ n فقط؟
تأتي قواسم العدد في أزواج d وn / d حاصل ضربهما هو n. إذا كان كلاهما أكبر من √n، فسيكون حاصل ضربهما أكبر من n. لذا يحتوي كل زوج على عنصر لا يتجاوز √n، وإذا لم يظهر أي قاسم حتى ذلك الحين، فإن n عدد أولي.
هل 1 عدد أولي؟
لا. للعدد الأولي قاسمان مختلفان بالضبط، هما 1 والعدد نفسه، أما 1 فله قاسم واحد فقط. استبعاد 1 يحافظ على فرادة تحليل كل عدد صحيح موجب إلى عوامل أولية. لهذا السبب، تُرجع isPrime(1) القيمة false.
هل توجد طريقة أسرع لاختبار أولية الأعداد الكبيرة جدًا؟
بالنسبة إلى عدد واحد من 32 بت، تكون القسمة التجريبية حتى √n سريعة بما يكفي. أما الأعداد التي تتكون من عشرات الخانات، فتستخدم البرامج اختبار Miller-Rabin، الذي يفحص بعض القوى بترديد معياري بدلًا من تجربة القواسم. ولإدراج كل عدد أولي حتى حد معين، تتفوق غربال إراتوستينس على اختبار كل عدد بمفرده.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def isPrime(n):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
n = 29
المتوقع
true