מספרים ראשוניים — מה זה ואיך מזהים

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

מספר ראשוני הוא מספר טבעי גדול מ-1 שמתחלק רק ב-1 ובעצמו.

דוגמאות

• 7 ראשוני — מתחלק רק ב-1 וב-7
• 6 לא ראשוני — מתחלק גם ב-2 וב-3

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

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

שימו לב: 2 הוא המספר הראשוני הזוגי היחיד!

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

שיטה 1: חלוקה בכל הראשוניים עד השורש

לבדיקת 97:

1. √97 ≈ 9.8, אז בודקים עד 9
2. מחלקים ב-2, 3, 5, 7
3. אף אחד לא מתחלק ← 97 ראשוני

שיטה 2: כללי חלוקה מהירים

• מתחלק ב-2? → מסתיים בספרה זוגית
• מתחלק ב-3? → סכום הספרות מתחלק ב-3
• מתחלק ב-5? → מסתיים ב-0 או 5

פירוק לגורמים ראשוניים

כל מספר טבעי ניתן לכתוב כמכפלה של ראשוניים:

60 = 2² × 3 × 5

84 = 2² × 3 × 7

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

• בסיס להצפנה (RSA)
• מציאת מ.ש.מ ומ.מ.מ
• צמצום שברים

נפת ארטוסתנס

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

1. רשום את כל המספרים מ-2 עד n
2. מחק את כל הכפולות של 2 (חוץ מ-2)
3. מחק את כל הכפולות של 3 (חוץ מ-3)
4. המשך עם 5, 7, 11... עד √n
5. מה שנשאר = ראשוניים!