הנפה של ארטוסתנס

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

(את המספר 1 אין כוללים ברשימה, משום שהוא לא נחשב לראשוני. ראו מספר ראשוני להסבר בעניין זה).

פסאודו קוד של נפת ארטוסתנס

SmallPrimeList
 
  Input:  n (n < 2^20)
  Output: P[] (a list of all primes <= n)
 
  1. b[n] = {1,1,...,1}. (a bit array of n one's).
 
  2. i = 2.
 
  3. While i * i <= n do:
        For j = 2 to n / i do:
           b[j * i] = 0.
        do:
           i = i + 1.
        While b[i] = 0
 
  4. For k = 2 to n do:
        If b[k] = 1 then
           add k to P[].
 
  5. Return P[].

דוגמה

מציאת כל המספרים הראשוניים בין 2 ל-120 באמצעות הנפה של ארטוסתנס.

להלן האלגוריתם עבור המספרים עד 20.

• רושמים את המספרים מ-2 ואילך, עד לגבול שקבענו מראש.

הרשימה: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

• צעד 1. מסמנים את המספר הראשון ברשימה כראשוני.

ראשוניים שמצאנו: 2
הרשימה: 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

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

ראשוניים שמצאנו: 2
הרשימה: 3 5 7 9 11 13 15 17 19

• צעד 2. אם המספר הגדול ביותר ברשימה קטן מהריבוע של המספר הגדול ביותר ברשימת הראשוניים שמצאנו, סמן את כל המספרים ברשימה כראשוניים; אחרת, סמן את המספר הראשון ברשימה כראשוני (כלומר, בדומה לצעד 1). אם מספר כלשהו לא מתחלק באף אחד מהמספרים עד לשורש הריבועי שלו, הוא בהכרח לא מתחלק גם במספרים גדולים יותר, ולכן הוא ראשוני.

מכיוון ש-19 גדול מהריבוע של 2 (השווה ל-4), מסמנים את המספר הראשון ברשימה כראשוני:

ראשוניים שמצאנו: 2 3
הרשימה: 5 7 9 11 13 15 17 19

• צעד 2 - המשך

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

ראשוניים שמצאנו: 2 3
הרשימה: 5 7 11 13 17 19

• צעד 3

19 גדול מהריבוע של 3 (שהוא 9), ממשיכים בדומה לצעד 1:

ראשוניים שמצאנו: 2 3 5
הרשימה: 7 11 13 17 19

• צעד 4

כעת 19 קטן מהריבוע של 5 (25) ולכן האלגוריתם יסתיים.

התוצאה: המספרים הראשוניים מ-2 עד 20 הם 2, 3, 5, 7, 11, 13, 17 ו-19.

קישורים חיצוניים

• הורדת יישום הפועל לפי שיטת הנפה של ארטוסתנס. (12KB, דורש Microsoft .NET framework, גרסה 4.0 לפחות)