המחשבון בודק אם מספר הוא ראשוני, ואם לא — מציג את הפירוק שלו לגורמים ראשוניים.
מספר ראשוני הוא מספר שלם גדול מ-1 שמתחלק רק ב-1 ובעצמו. 97 ראשוני; 1001 אינו, והוא 7 × 11 × 13.
בדיקת ראשוניות ופירוק לגורמים
לבדיקת ראשוניות די לבדוק מחלקים עד השורש של המספר. אם ל-n יש מחלק גדול מהשורש, חייב להיות לו גם מחלק קטן ממנו — שכבר נבדק. לכן במקום 10,000 בדיקות ל-n של 10,000, מספיקות 100.
הפירוק לגורמים ראשוניים עובד באותו עיקרון: מחלקים במחלק הקטן ביותר שנמצא, חוזרים על התהליך עם המנה, וממשיכים עד שלא נשאר מה לחלק.
המשפט היסודי של האריתמטיקה קובע שלכל מספר שלם גדול מ-1 יש פירוק יחיד לגורמים ראשוניים, עד כדי סדר הגורמים. 360 הוא תמיד 2³ × 3² × 5 ולא שום דבר אחר.
1 אינו ראשוני ואינו פריק. הוא מוחרג בכוונה — אם הוא היה ראשוני, הייחידות של הפירוק הייתה נשברת, כי אפשר היה להוסיף לכל פירוק כמה 1־ים שרוצים.
2 הוא הראשוני הזוגי היחיד. כל זוגי אחר מתחלק ב-2, ולכן אינו ראשוני בהגדרה.
דוגמאות
- 97: ראשוני. די לבדוק עד שורש 97, כלומר עד 9 — ו-2, 3, 5, 7 אינם מחלקים אותו
- 360: 2 × 2 × 2 × 3 × 3 × 5, כלומר 2³ × 3² × 5
- 1001: 7 × 11 × 13 — נראה ראשוני אבל אינו
- 1: אינו ראשוני ואינו פריק, לפי הגדרה
- 2: ראשוני, והזוגי היחיד ביניהם
הראשוניים עד 100
יש 25 מספרים ראשוניים עד 100:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
| עד | כמה ראשוניים | הצפיפות |
|---|---|---|
| 10 | 4 | 40% |
| 100 | 25 | 25% |
| 1,000 | 168 | 16.8% |
| 10,000 | 1,229 | 12.3% |
| 1,000,000 | 78,498 | 7.8% |
הראשוניים מתדללים בהדרגה, אבל לעולם לא נגמרים — אוקלידס הוכיח זאת לפני כ-2,300 שנה. ההוכחה אלגנטית: בהינתן רשימה סופית של ראשוניים, מכפילים את כולם ומוסיפים 1. המספר שמתקבל אינו מתחלק באף אחד מהם, ולכן או שהוא ראשוני חדש או שיש לו גורם ראשוני שלא ברשימה.
למה זה חשוב מחוץ למתמטיקה
האבחנה המעשית: לכפול שני ראשוניים גדולים זה קל, ולפרק את התוצאה חזרה זה קשה מאוד. על האסימטריה הזו בנויה הצפנת RSA, שמאבטחת חלק גדול מהתקשורת באינטרנט.
מכפלה של שני ראשוניים בני 300 ספרות כל אחד מחושבת מיד. פירוק המכפלה חזרה לגורמיה הוא מעבר ליכולת של מחשבים קיימים בפרק זמן סביר — ובזה בדיוק נשמר הסוד.
שתי שאלות פתוחות מוכרות סביב ראשוניים:
- השערת התאומים: האם יש אינסוף זוגות ראשוניים שההפרש ביניהם 2, כמו 11 ו-13? טרם הוכחה.
- השערת גולדבך: האם כל זוגי גדול מ-2 הוא סכום שני ראשוניים? נבדקה עד מספרים עצומים ועדיין ללא הוכחה.
שאלות נפוצות
מה זה מספר ראשוני?
מספר שלם גדול מ-1 שמתחלק רק ב-1 ובעצמו. 97 ראשוני, 1001 אינו — הוא 7 × 11 × 13.
האם 1 ראשוני?
לא. הוא מוחרג בכוונה, כדי שהפירוק לגורמים ראשוניים יהיה יחיד — אחרת היה אפשר להוסיף לכל פירוק כמה 1־ים שרוצים.
עד איזה מספר צריך לבדוק מחלקים?
עד השורש של המספר. אם יש מחלק גדול מהשורש, בהכרח יש גם מחלק קטן ממנו שכבר נבדק.
האם יש אינסוף מספרים ראשוניים?
כן, ואוקלידס הוכיח זאת. הם מתדללים בהדרגה — עד 100 יש 25 ועד מיליון יש 78,498 — אבל לא נגמרים.
למה ראשוניים חשובים באבטחת מידע?
מפני שכפל שני ראשוניים גדולים קל וחישובי, ופירוק התוצאה חזרה קשה מאוד. הצפנת RSA בנויה בדיוק על הפער הזה.