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

ב[[תורת המספרים]], '''ה[[מסננת|נפה]] של ארטוסתנס''' הוא [[אלגוריתם]] פשוט למציאת כל ה[[מספר ראשוני|מספרים הראשוניים]] עד ל[[מספר שלם]] מסוים. הנפה הומצאה על ידי המתמטיקאי היווני [[ארטוסתנס]] .

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

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

^ ^ ^ ^ ^ ^ ^ ^ ^

4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

- - - ^ - ^- - ^ - ^- -

2 3

2 3 5 7 11 13 17 19

Input: n (whole number)

Output: P[] (a list of all primes <= n)

1. b[n] := {1,1,...,1}. (a bit array of n one's, 1-based).

2. For i = 2 while i * i <= n step 1 do:

If b[i] == 1 then

For j = i * i to n step i do:

b[j] := 0.

3. For k = 2 to n do:

If b[k] == 1 then

add k to P[].

4. Return P[].

* ארי שביב, [https://davidson.weizmann.ac.il/online/mathcircle/articles/%D7%94%D7%A0%D7%A4%D7%94-%D7%A9%D7%9C-%D7%90%D7%A8%D7%98%D7%95%D7%A1%D7%AA%D7%A0%D7%A1 הנפה של ארטוסתנס], באתר [[מכון דוידסון]], אוקטובר 2014

* {{MathWorld}}