מספר ראשוני הוא מספר טבעי גדול מ-1 שיש לו רק שני מחלקים: 1 ועצמו. המספרים הראשוניים הראשונים: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... 2 הוא המספר הראשוני הזוגי היחיד. לבדיקה אם n הוא ראשוני, מספיק לאמת שn אינו מתחלק בשום מספר ראשוני עד √n. נפת ארטוסתנס היא שיטה יעילה למציאת כל המספרים הראשוניים עד מספר נתון. למספרים ראשוניים יש יישומים מפתח בקריפטוגרפיה ואבטחת מידע.