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

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

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

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

המספר 1 לא כלול כי הוא אינו נחשב לראשוני.

להלן התהליך בקיצור עבור המספרים 2 עד 20. בסוף נשארים המספרים הראשוניים: 2 3 5 7 11 13 17 19. המספרים האחרים סומנו כחסרי ראשוניות על ידי סימון הכפולות שלהם.

הרעיון בפסאודו‑קוד הוא לשמור מערך של ערכי בוליאן מאינדקס 2 עד n, את כולם מתחילים כ"אמת". עוברים על i מ‑2 עד √n. אם A[i] עדיין "אמת", משנים ל"שקר" את כל A[j] עבור j = i², i²+i, i²+2i,... עד n. בסוף מחזירים את כל האינדקסים שעדיין "אמת".

דוגמה בפייתון יוצרת רשימת אמת/שקר בגודל n-1, עושה לולאה על i עד שורש n, ומסמנת False לכל הכפולות של i. בסוף מחזירה את המספרים שסומנו True כראשוניים.

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

ככה עובדים: כותבים את המספרים מ‑2 ועד n. מקפידים על המספר הכי קטן שלא סומן. הוא ראשוני. מוחקים את כל הכפולות שלו. כפולה היא תוצאה של הכפלה, למשל 3 כפול 2 שווה 6. חוזרים על זה עם המספר הבא שלא סומן.

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

עבור 2 עד 20 נשארים: 2 3 5 7 11 13 17 19.

משתמשים במערך של אמת/שקר כדי לסמן מי ראשוני. מסמנים כ"שקר" את הכפולות החל מ‑p².

קיים קוד קצר שמכין רשימת אמת/שקר, מסמן את הכפולות ומחזיר את הראשוניים.