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