הנפה של ארטוסתנס
בתורת המספרים, הנפה של ארטוסתנס הוא אלגוריתם פשוט למציאת כל המספרים הראשוניים עד למספר שלם מסוים. הנפה הומצאה על ידי המתמטיקאי היווני ארטוסתנס. מתחילים עם רשימת כל המספרים השלמים מ-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[].
[עריכה] דוגמה
להלן האלגוריתם עבור המספרים עד 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 לפחות)
