מחשבון מספרים ראשוניים

מחשבון מספרים ראשוניים - סכום, ספירה וחיפוש ראשוניים

🔢 חשבו סכום של מספרים ראשוניים, מצאו ראשוניים בטווח, בדקו אם מספר הוא ראשוני, ומצאו את הראשוני ה־n. אלגוריתם מסננת ארטוסתנס מהיר עם הדמיה.

מהם מספרים ראשוניים?

מספר ראשוני הוא מספר טבעי גדול מ־1 שלא ניתן ליצור באמצעות כפל של שני מספרים טבעיים קטנים יותר. במילים אחרות, יש לו בדיוק שני מחלקים: 1 והוא עצמו.

25 המספרים הראשוניים הראשונים

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

איך לבדוק אם מספר הוא ראשוני

שיטה 1 - חלוקה נסיונית:

• בדקו אם n מתחלק באחד המספרים מ־2 עד √n
• אם כן – הוא מורכב (לא ראשוני)
• אם לא – הוא ראשוני

דוגמה: האם 17 ראשוני?

• √17 ≈ 4.12, לכן בודקים חלוקה ב־2, 3, 4
• 17 ÷ 2 = 8.5 (לא מתחלק)
• 17 ÷ 3 = 5.67 (לא מתחלק)
• 17 ÷ 4 = 4.25 (לא מתחלק)
• תוצאה: 17 ראשוני!

מסננת ארטוסתנס

אלגוריתם עתיק למציאת כל הראשוניים עד n:

• שלב 1: רשמו את כל המספרים מ־2 עד n
• שלב 2: סמנו את 2 כראשוני ומחקו את כל הכפולות של 2
• שלב 3: מצאו את המספר הבא שלא נמחק (3) וסמנו כראשוני
• שלב 4: מחקו את כל הכפולות של אותו ראשוני
• שלב 5: חזרו על הפעולה עד √n
• תוצאה: כל המספרים שלא נמחקו הם ראשוניים

סכום מספרים ראשוניים

סכום n הראשוניים הראשונים:

• 10 הראשוניים הראשונים: 2+3+5+7+11+13+17+19+23+29 = 129
• 100 הראשוניים הראשונים: סכום = 24,133
• 1000 הראשוניים הראשונים: סכום = 3,682,913

סכום ראשוניים עד n:

• עד 10: 2+3+5+7 = 17
• עד 100: סכום = 1,060
• עד 1000: סכום = 76,127

משפט המספרים הראשוניים

מספר הראשוניים הקטנים מ־n הוא בקירוב n/ln(n):

• עד 100: ~25 ראשוניים (בפועל: 25)
• עד 1,000: ~145 ראשוניים (בפועל: 168)
• עד 10,000: ~1,086 ראשוניים (בפועל: 1,229)
• עד 100,000: ~8,686 ראשוניים (בפועל: 9,592)

סוגי מספרים ראשוניים

ראשוניים תאומים: ראשוניים שההפרש ביניהם הוא 2

• (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)...

ראשוניים של מרסן: מהצורה 2ᵖ - 1 כאשר p ראשוני

• 2² - 1 = 3
• 2³ - 1 = 7
• 2⁵ - 1 = 31
• 2⁷ - 1 = 127
• המספר הראשוני הגדול ביותר הידוע הוא מרסן (24.8 מיליון ספרות!)

ראשוניים של סופי ז'רמן: ראשוני p כך ש־2p+1 גם ראשוני

• 2 (2×2+1 = 5), 3 (2×3+1 = 7), 5 (2×5+1 = 11), 11, 23, 29...

ראשוניים של פרמה: מהצורה 2^(2ⁿ) + 1

• F₀ = 3, F₁ = 5, F₂ = 17, F₃ = 257, F₄ = 65,537
• ידועים רק 5 ראשוניים של פרמה

יישומים של מספרים ראשוניים

קריפטוגרפיה (RSA):

• מבוסס על הקושי לפרק מספרים גדולים לגורמים
• משתמש בשני ראשוניים גדולים (מאות ספרות)
• מאבטח בנקאות מקוונת, אימיילים ואתרים

טבלאות גיבוב:

• טבלאות בגודל ראשוני מפחיתות התנגשויות
• משמשות במסדי נתונים וב־caching

יצירת מספרים אקראיים:

• ראשוניים יוצרים רצפים פסאודו-אקראיים טובים יותר
• משמשים בסימולציות ובמשחקים

עובדות מעניינות על ראשוניים

• אינסופיות: הוכח ע״י אוקלידס ~300 לפנה״ס – הראשוניים לא נגמרים
• פערים: יכולים להיות גדולים מאוד
• השערת גולדבך: כל מספר זוגי > 2 הוא סכום של שני ראשוניים (לא הוכח!)
• השערת רימן: פרס של מיליון דולר להוכחה על התפלגות הראשוניים
• פערי ראשוניים: ההפרש בין ראשוניים עוקבים גדל
• הסתברות: למספר אקראי n יש ~1/ln(n) סיכוי להיות ראשוני

שיאים

• הראשוני הגדול ביותר הידוע: 2^82,589,933 - 1 (2018, 24,862,048 ספרות)
• הראשוניים התאומים הגדולים ביותר: 2,996,863,034,895 × 2^1,290,000 ± 1
• חישוב: GIMPS (Great Internet Mersenne Prime Search) פרויקט מבוזר

טעויות נפוצות

• 1 אינו ראשוני: לפי ההגדרה המודרנית (בדיוק 2 מחלקים)
• לא כל המספרים האי-זוגיים ראשוניים: 9, 15, 21, 25... הם מורכבים
• נוסחה לכל הראשוניים: אין נוסחה פשוטה שמייצרת את כולם
• דפוס בראשוניים: אין דפוס צפוי (נראים אקראיים)

💡 טיפ: כדי לבדוק אם מספר גדול הוא ראשוני, מספיק לבדוק חלוקה עד השורש הריבועי שלו! למשל, כדי לבדוק אם 997 ראשוני, צריך לבדוק עד √997 ≈ 31.6: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. אם אף אחד לא מחלק את 997 ללא שארית, הוא ראשוני! בנוסף, למעט 2 ו־3, כל הראשוניים הם מהצורה 6k±1.