מחולל מספרים ראשוניים אונליין
מהו מספר ראשוני?
מספר ראשוני הוא מספר טבעי גדול מ-1 שמתחלק רק ב-1 ובעצמו. המספרים הראשוניים הקטנים ביותר הם 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… המספר 2 הוא המספר הראשוני הזוגי היחיד – כל שאר המספרים הזוגיים מתחלקים בשניים.
מספרים כמו 4 (= 2 × 2), 6 (= 2 × 3) או 15 (= 3 × 5) אינם מספרים ראשוניים – אנו קוראים להם מספרים פריקים (או מורכבים).
איך המחולל עובד?
כדי להציג את כל המספרים הראשוניים בטווח נתון, אנו משתמשים בנפת ארטוסתנס – אחד האלגוריתמים הוותיקים והיעילים ביותר, שתואר על ידי המתמטיקאי היווני ארטוסתנס מקירנה בסביבות שנת 240 לפני הספירה.
האלגוריתם מוחק בהדרגה את הכפולות של כל מספר ראשוני שנמצא. מה שנותר הם המספרים הראשוניים. כל החישוב מתבצע ישירות בדפדפן שלך – ללא שליחת נתונים לשרת.
לבחירה אקראית, המחולל בונה תחילה רשימה של כל המספרים הראשוניים בטווח, ולאחר מכן בוחר מתוכה באופן אקראי את הכמות הרצויה באמצעות מחולל בטוח מבחינה קריפטוגרפית (crypto.getRandomValues()).
תכונות המחולל
- כל המספרים הראשוניים – מציג כל מספר ראשוני בטווח הנתון (מקסימום 10,000)
- בחירה אקראית – בוחר N מספרים ראשוניים אקראיים מהטווח (מתאים לטווחים גדולים)
- מיון – ממיין את התוצאות בסדר עולה
- מפריד – בחר כיצד המספרים יופרדו בעת ההעתקה
- הגדרות קבועות מהירות – טווחים נפוצים בלחיצה אחת
היכן משתמשים במספרים ראשוניים?
קריפטוגרפיה ואבטחה
מספרים ראשוניים הם אבן היסוד של הקריפטוגרפיה המודרנית. אלגוריתמים כמו RSA פועלים על העיקרון שקל לחשב את מכפלתם של שני מספרים ראשוניים גדולים, אך פירוקם לגורמים ראשוניים לאחור הוא קשה חישובית.
- הצפנת RSA – מפתחות נוצרים משני מספרים ראשוניים גדולים
- דיפי-הלמן (Diffie-Hellman) – החלפת מפתחות מעל מודולו ראשוני
- פונקציות גיבוב (Hash) – מספרים ראשוניים כקבועים קסומים (SHA, MD5)
מתמטיקה ומדע
- תורת המספרים – אבני הבניין הבסיסיות של המספרים השלמים
- השערת גולדבך – כל מספר זוגי > 2 ניתן לביטוי כסכום של שני מספרים ראשוניים (טרם הוכחה)
- השערת רימן – אחת מבעיות הילברט, נוגעת להתפלגות המספרים הראשוניים
שימושים מעשיים
- טבלאות גיבוב (Hash Tables) – גודל טבלה כמספר ראשוני מפחית התנגשויות
- מחוללי מספרים פסאודו-אקראיים – קונגרואנציה לינארית עם מודולו ראשוני
- מוזיקה וקצב – פוליריתמיקה עם אורכי מחזור ראשוניים
התפלגות המספרים הראשוניים
מספרים ראשוניים מפוזרים באופן לא סדיר בין המספרים הטבעיים, אך צפיפותם יורדת ככל שהטווח גדל. עובדה זו מתוארת על ידי משפט המספרים הראשוניים: מספר המספרים הראשוניים עד N הוא בקירוב N / ln(N).
| טווח | כמות מספרים ראשוניים |
|---|---|
| 1–10 | 4 |
| 1–100 | 25 |
| 1–1,000 | 168 |
| 1–10,000 | 1,229 |
| 1–100,000 | 9,592 |
| 1–1,000,000 | 78,498 |
נפת ארטוסתנס צעד אחר צעד
טווח 2–30:
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
1. בחר 2, מחק כפולות: 4, 6, 8, 10, 12...
2. בחר 3, מחק כפולות: 9, 15, 21, 27...
3. בחר 5, מחק כפולות: 25...
4. √30 ≈ 5.5 → הסתיים
מספרים ראשוניים: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29נפת ארטוסתנס בקוד
JavaScript
function sieve(to) {
const composite = new Uint8Array(to + 1);
const primes = [];
for (let p = 2; p <= to; p++) {
if (composite[p]) continue;
primes.push(p);
for (let j = p * p; j <= to; j += p) composite[j] = 1;
}
return primes;
}Python
def sieve(n):
composite = bytearray(n + 1)
primes = []
for p in range(2, n + 1):
if not composite[p]:
primes.append(p)
for j in range(p * p, n + 1, p):
composite[j] = 1
return primes