➗בדיקת מספר ראשוני

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

מספר ראשוני הוא מספר שלם גדול או שווה ל-2 שאין לו מחלקים מלבד 1 והמספר עצמו. מספרים כמו 2, 3, 5, 7, 11 הם ראשוניים, ו-2 הוא המספר הראשוני הזוגי היחיד.

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

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

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

כדי לבדוק האם מספר שלם n הוא ראשוני, מחלקים אותו ברצף במספרים עד √n, ואם אף אחד מהם אינו מחלק אותו ללא שארית, המספר ראשוני. לדוגמה, 91 מתחלק ב-7, שהוא קטן או שווה ל-√91 (כ-9.5), ולכן אינו ראשוני.

• שיטת חלוקת ניסיון：שיטת חלוקת ניסיון מחלקת את n ברצף במספרים מ-2 עד √n כדי למצוא מחלקים, אך ככל שמספר הספרות גדל, מספר החלוקות הנדרשות גדל בצורה עצומה.
• שיטת מילר-רבין：שיטת מילר-רבין בודקת שאריות של חזקות עבור מספר ‘בסיסים’ נבחרים כדי למצוא עדות לכך שהמספר אינו ראשוני, ומאפשרת בדיקה מהירה גם עבור מספרים גדולים.