מספר פריק

מספר פָּרִיק הוא מספר שלם חיובי שאפשר לכתוב אותו כמכפלה של שני שלמים גדולים מ-1. מספרים אלה נקראים 'גורמים' של המספר הנתון. כל מספר שלם גדול מ-1 הוא ראשוני או פריק. לדוגמה, המספר 14 הוא פריק מכיוון שאפשר לפרק אותו כמכפלה של 2 ו-7, ולכן 2 ו- 7 הם הגורמים של 14.

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

מספר $\ 4<n$ הוא פריק אם ורק אם $\ (n-1)!\equiv 0{\pmod {n}}$ (לשם השוואה, משפט וילסון: אם n ראשוני אז $\ (n-1)!\equiv -1{\pmod {n}}$ ).

בדיקת פריקות ומציאת גורמים

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

על מבחנים מתמטיים הבודקים פריקות של מספר, ראו בדיקת ראשוניות. בדרך-כלל מבחנים אלה מזהים שהמספר פריק בלי למצוא לו מחלק, והם מהירים בהרבה מכל שיטה המוצאת מחלק במפורש.

השיטות המהירות ביותר לפירוק מספר גדול הן שיטת הנפה הריבועית ושיטת הנפת שדה מספרים. זמן הריצה של שיטות אלה תלוי רק בגודלו של המספר שאותו מבקשים לפרק. בהשוואה אליהן, שיטת רו של פולארד היא אלגוריתם הסתברותי, המוצא מחלק של n בזמן שהוא בקירוב ${\sqrt {p}}$ , כאשר p הוא המחלק הקטן ביותר (שכמובן אינו ידוע מראש). שיטה זו עדיפה, אם כן, כאשר ידוע שלמספר יש גורם ראשוני קטן יחסית.