כאשר סופרים את הראשוניים בקטעים ארוכים (כגון: עד 1000, בין 1000 ל-2000, וכן הלאה), מגלים ששכיחותם הולכת ויורדת. גאוס עסק רבות בחישובים בקשר לסוגיה זו, ושיער ששכיחות הראשוניים בין 1 ל-x יורדת, בקירוב, ביחס הפוך ללוגריתם הטבעי של x. כחמישים שנים אחר-כך חקר רימן את פונקציית זטא הקרויה על שמו, במטרה להוכיח את ההשערה של גאוס. על היסודות שהניח רימן, הצליחו לבסוף המתמטיקאים של סוף המאה ה-19 להוכיח את משפט המספרים הראשוניים: מספר הראשוניים הקטנים ממספר נתון formula_5 שווה בקירוב ל- :formula_6
כאשר formula_7 הוא הלוגריתם הטבעי של formula_8.
ממשפט המספרים הראשוניים אפשר להסיק היכן נמצא, בקירוב, הראשוני ה-n-י, formula_9:
formula_10. ליתר דיוק, עבור כל שלם formula_11, מתקיים
formula_12.
לפי השערת ברטראן (שהוכחה במאה ה-19), יש מספר ראשוני בכל קטע מהצורה formula_13. עם זאת, לא ידוע האם לכל n טבעי קיימים ראשוניים בקטע formula_14.
ברווח שבין ראשוניים סמוכים עוסקת השערת המספרים הראשוניים התאומים.
הצגות של ראשוניים.
לא קיים פולינום שאינו קבוע, אפילו בכמה משתנים, המקבל (כאשר מציבים בו מספרים שלמים) רק ערכים ראשוניים. לתוצאה זו יש הכללות רבות. למשל, היא נכונה גם עבור פונקציות אלגבריות (פונקציה F היא אלגברית אם קיים פולינום P כך ש- formula_15; לדוגמה, formula_16 אלגברית). פונקציה מהצורה formula_17, שבה הפולינומים formula_18 בעלי מקדמים שלמים, והמספרים formula_19 שלמים, שאינה קבועה, אינה יכולה לקבל רק ערכים ראשוניים כאשר מציבים במשתנים formula_20 ערכים טבעיים.
לעומת זאת, אפשר להציג מספרים ראשוניים באמצעות פונקציות שאינן אלגבריות. לדוגמה, אם מגדירים את הפונקציה formula_21, ו- formula_22 היא השארית של y בחלוקה ל- x (עם formula_23), אז הראשוני ה-n-י מתקבל מהנוסחה formula_24. בעזרת טכניקות שפותחו במסגרת פתרון הבעיה העשירית של הילברט, נמצאו פולינומים formula_25 בעלי מקדמים שלמים, כך שקבוצת הערכים הטבעיים שהפולינום מקבל, כאשר מציבים ב- formula_20 מספרים טבעיים, מתלכדת עם קבוצת המספרים הראשוניים.
משפט מילס קובע כי קיים קבוע formula_27 כך ש-formula_28 ראשוני לכל n טבעי (כאשר formula_29 היא פונקציית הערך השלם).
הצגות ויזואליות של ראשוניים.
צורה ויזואלית של התפלגות המספרים הראשוניים ניתנת להצגה על ידי ספירלת אולם. אופן הצגה זה מדגיש את הראשוניים המופיעים בסדרות ריבועיות, כמו formula_30. את הספירלה גילה המתמטיקאי ומדען האטום סטניסלב אולם.
ראשוניים בסדרות חשבוניות.
את משפט המספרים הראשוניים הכליל דיריכלה לסדרות חשבוניות:
אם formula_31 הם מספרים זרים, אז ישנם אינסוף מספרים ראשוניים השקולים ל-formula_32 מודולו formula_33. דיריכלה הוכיח שבכל formula_33, המספרים הראשוניים מפוזרים באופן אחיד בקירוב, בין formula_35 השאריות האפשריות מודולו formula_33. אם formula_37 מייצג את כל המספרים הראשוניים בטווח formula_38 השקולים ל-formula_32 מודולו formula_33, כאשר formula_41, אזי
לעומת זאת, לא ידוע האם יש אינסוף ראשוניים מצורות שאינן ליניאריות, כגון formula_43.
טורים ומכפלות אינסופיות.
ידוע שסכום הטור ההרמוני formula_44 הוא formula_45 (כאשר formula_46 הוא קבוע אוילר-מסקרוני). לעומת זאת, כאשר מסכמים על ראשוניים בלבד, formula_47, כאשר B קבוע. ובפרט טור ההופכיים של המספרים הראשוניים מתבדר.
באופן דומה, המכפלה formula_48, בעוד ש- formula_49.
ראשוניים קטנים וגדולים.
המספרים הראשוניים הקטנים ביותר הם 2, 3, 5, 7, 11, 13 ו-17.
נכון ל-2019, המספר הראשוני הגדול ביותר שהתגלה הוא מספר מרסן הראשוני ה-51, formula_50. למספר זה 24,862,048 ספרות עשרוניות. המספר התגלה באמצעות חישוב מבוזר קהילתי של מיזם GIMPS על ידי פטריק לארוץ'. קדם לו המספר formula_51 שהתגלה ב-26 בדצמבר 2017 שהוא מספר מרסן הראשוני ה-50, שהתגלה על ידי ג'ון פייס ממיזם GIMPS.
אלגוריתמים.
מאז המצאת שיטת RSA ב-1977, הפכו המספרים הראשוניים למרכיב יסודי כמעט בכל מערכת הצפנה המשלבת מפתחות ציבוריים ופרטיים. במקרים רבים, חוזק ההצפנה מבוסס על הקלות היחסית שבה אפשר לבצע פעולות של כפל והעלאה בחזקה מודולריות, גם במספרים גדולים (בני מאות ספרות), ומאידך על הקושי העצום שבפירוק מספרים כאלה לגורמיהם הראשוניים.
מציאת כל המספרים הראשוניים הקטנים ממספר נתון.
ארטוסתנס, מתמטיקאי ואסטרונום יווני בן המאה ה-3 לפנה"ס, פיתח אלגוריתם פשוט ויעיל למציאת כל המספרים הראשוניים הקטנים ממספר נתון, הקרוי על שמו: הנפה של ארטוסתנס. אלגוריתם זה מאתר מספרים ראשוניים בהדרגה ככאלה שאינם מספרים פריקים, אשר אותם הוא מפיק עבור כל מספר ראשוני, החל מ 2, על ידי ספירה בכפולות של אותו מספר. לדוגמה:
קובעים 2 כמספר ראשוני הראשון, סופרים ממנו בצעדים של 2 ומסמנים את כל המספרים האלה (שיהיו המספרים הזוגיים) כפריקים. קובעים ש 3 הוא הראשוני הבא ומסמנים את כפולותיו על ידי ספירה בשלשות (יהיו אלה כל הכפולות של 3). 5 הוא הראשוני הבא (את 4 סימנו כבר בשלב הראשון), ואת כפולותיו מסמנים על ידי ספירה בצעדים של 5, וכך הלאה.
הנפה של ארטוסתנס יעילה מבחינת סיבוכיות הזמן הנדרש לביצוע המשימה ליצירת רשימה של מספרים ראשוניים הקטנים מגבול מסוים, אך אינה יעילה לבדיקת ראשוניות של מספר נתון; לשם כך יש דרכים אחרות.
הוכחת ראשוניות.
כדי להוכיח שמספר נתון אינו ראשוני, די להציג פירוק שלו לשני גורמים. מכאן שזיהוי מספרים לא ראשוניים הוא בעיה שהיא לפחות במחלקת הסיבוכיות NP. גם בדיקה האם מספר הוא ראשוני שייכת ל-NP, בהתבסס על כך שמספר p הוא ראשוני אם ורק אם קיים מספר מסדר p-1 בחבורת אוילר של p, ותנאי זה ניתן לבדיקה באופן יעיל בהינתן הפירוק של p-1 (כך שהוכחת NP לראשוניות p תכלול את הפירוק הזה ואת המספר מסדר p-1). בשנת 2002 הציגו מנינדרה אגרוול, נירג' קייל וניטין סקסנה אלגוריתם פולינומי להוכחת ראשוניות, הנקרא על שמם מבחן AKS לראשוניות. בכך הראו שהוכחת ראשוניות שייכת למחלקת הסיבוכיות P ולפיכך גם הבעיה הדואלית (האם מספר אינו ראשוני) שייכת ל-P.
מבחני ראשוניות.
הדרך הנאיבית לבדיקת ראשוניות של מספר נתון נקראת "חלוקה ניסיונית" (Trial division): ניסיון לחלק את המספר הנתון בכל המספרים מ־2 ועד לשורש הריבועי של המספר הנתון. אם המספר לא התחלק באף אחד ממספרים אלו הוא גם לא יתחלק באף מספר גדול יותר ולכן הוא ראשוני. במספרים קטנים (ובסמוך להפעלת שיטת הנפה של ארטוסתנס), עדיף לבצע את החילוק הניסיוני רק במספרים ראשוניים. לשתי השיטות סיבוכיות formula_52 או קרוב לזה, והן אינן יעילות עבור מספרים גדולים (בני עשרות ספרות עשרוניות).
אלגוריתמים מתקדמים יותר לבדיקת ראשוניות מתחלקים לשני סוגים עיקריים:
מבחנים רבים, משתי המחלקות, מבוססים על המשפט הקטן של פרמה: עבור כל ראשוני formula_53 ושלם formula_32 זר ל-formula_53, מתקיים השוויון formula_56. לפיכך, אם השוויון אינו מתקיים, זוהי ראיה לכך ש- formula_53 אינו ראשוני. קיימים אלגוריתמים יעילים לחישוב הערך של formula_58 מודולו formula_33, כגון אלגוריתם ריבוע וכפל (העלאה חוזרת בריבוע, וכפל ב-a על-פי ההצגה הבינארית של n), שסיבוכיותו פולינומית באורך של n. כל מספר ראשוני יעבור את המבחן, אולם לכל a ישנם מספרים פריקים שהמבחן לא יאתר - אלו קרויים פסאודו ראשוניים.
גרי מילר ניצל תכונות ידועות של המשפט הקטן של פרמה ליצירת אלגוריתם דטרמיניסטי פולינומי למבחן ראשוניות, המתבסס על השערת רימן המוכללת (ERH). מיכאל רבין הרחיב את האלגוריתם מיד לאחר מכן, למבחן ראשוניות פולינומי אקראי. האלגוריתם נקרא על שמם אלגוריתם מילר-רבין. רוברט סולוביי ופולקר שטראסן הציעו אלגוריתם למבחן ראשוניות אקראי המבוסס על סימן יעקובי. עבור formula_33 ראשוני כלשהו formula_61 מתקיים עבור כל formula_32. גם אלגוריתם זה ניתן להרחבה למבחן ראשוניות דטרמיניסטי, בהנחה שהשערת רימן המורחבת נכונה.
שפי גולדווסר וג'ו קיליאן הציעו אלגוריתם אקראי למבחן ראשוניות המתבסס על עקום אליפטי, שזמן הריצה שלו פולינומי כמעט עבור כל קלט. בהתבסס על רעיון זה, פיתח ארתור אטקין אלגוריתם דטרמיניסטי יעיל מאוד מבחינה מעשית לבדיקת ראשוניות הנקרא Atkin's test. יתרונה של הגישה הוא שהיא מספקת הוכחות קצרות לראשוניות (primality certificate).
לאונרד אדלמן והואנג פרסמו אלגוריתם הסתברותי שלעולם אינו טועה, אולם רק ניתן לומר שתוחלת זמן הריצה שלו פולינומית, כלומר הם הראו שבדיקת ראשוניות היא במחלקת הסיבוכיות ZPP = RP ∩ Co-RP.
מבחינה תאורטית לפחות סוגיית הסיבוכיות של בדיקת ראשוניות יושבה ב-2002 כששלושה מדעני מחשב הודיים, אגרוול, קייל וסקסנה, הראו אלגוריתם פולינומי דטרמיניסטי לבדיקת ראשוניות הנקרא על שמם AKS. האלגוריתם מבוסס על הכללה של המשפט הקטן של פרמה לחוגי פולינומים מעל שדות סופיים. סיבוכיות האלגוריתם היא בסביבות formula_63.
איברים ראשוניים בתחומי שלמות.