הנפה של ארטוסתנס – הבדלי גרסאות

[[קובץ:Sieve_of_Eratosthenes_animation.gif|שמאל|ממוסגר|מציאת כל המספרים הראשוניים בין 2 ל-120 באמצעות הנפה של ארטוסתנס, כשהסימון מתחיל ממספר בריבוע.]]

 

 

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

את הכפולות מוצאים על ידי ספירה מהמספר כלפי מעלה בצעדים של אותו מספר. למשל, עבור ''3: 6, 9, 12, 15, ...'' . יהיו גם מספרים שיסומנו יותר מפעם אחת, למשל ''15 = 3 * 5 = 5 * 3''. לכן את הספירה ניתן להתחיל מהמספר בריבוע. כמו כן ניתן לעבוד עם המספרים האי־זוגיים בלבד ולספור בצעדים כפולים, למשל עבור ''5: 25, 35, 45, 55, ...'' .

 

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

 

==דוגמה==