Check Prime Number
מספר ראשוני הוא מספר שלם הגדול מ־1 שהמחלקים היחידים שלו הם 1 והוא עצמו. ניתן לך מספר שלם חיובי n. החזר true אם n הוא ראשוני, ואחרת החזר false. המספר 1 אינו ראשוני.
פונקציה
- ninteger
- המספר השלם החיובי לבדיקה
- מחזירהboolean
- true אם n הוא מספר ראשוני, אחרת false
אילוצים
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, ואחד מהשניים לכל היותר√n. אפשר לעצור ברגע ש-d * dעובר אתn.תחילה שלול את
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 מהירה מספיק. עבור מספרים בני עשרות ספרות, תוכניות משתמשות במבחן מילר-רבין, שבודק כמה חזקות מודולריות במקום לנסות מחלקים. כדי לרשום את כל המספרים הראשוניים עד גבול מסוים, נפת ארטוסתנס יעילה יותר מבדיקת כל מספר בנפרד.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def isPrime(n):
# כתבו כאן את הקודמקרה 1
מקרה 2
מקרה 3
קלט
n = 29
צפוי
true