הנפה של ארטוסתנס
אלגוריתם פשוט ויעיל למציאת כל המספרים הראשוניים עד למספר שלם מסוים / ויקיפדיה האנציקלופדיה encyclopedia
בתורת המספרים, הנָפָה של אֵרָטוֹסְתֶנֶס הוא אלגוריתם פשוט ויעיל למציאת כל המספרים הראשוניים עד למספר שלם מסוים. המצאת הנפה מיוחסת למתמטיקאי היווני ארטוסתנס.
מתחילים עם רשימת כל המספרים השלמים מ-2 ועד המספר הנבחר n. בכל שלב, מכריזים על המספר הקטן ביותר הלא מסומן ברשימה שעוד לא טופל כעל מספר ראשוני, ומסמנים בתוך הרשימה את כל הכפולות שלו (שהם יהיו מספרים פריקים). ממשיכים לבצע שלב אחרי שלב, כל עוד זה אפשרי.
בסופו של תהליך, כל המספרים ברשימה שלא סומנו הם כל המספרים הראשוניים מ-2 עד n.
את הכפולות מוצאים על ידי ספירה מהמספר כלפי מעלה בצעדים של אותו מספר. למשל, עבור 3: 6, 9, 12, 15, ... . יהיו גם מספרים שיסומנו יותר מפעם אחת, למשל 15 = 3 * 5 = 5 * 3. לכן את הספירה ניתן להתחיל מהמספר בריבוע (למשל 9 עבור 3, מכיוון ש 6 כבר יהיה מחוק בספירה מ 2). כמו כן ניתן לעבוד עם המספרים האי־זוגיים בלבד ולספור בצעדים כפולים, למשל עבור 5: 25, 35, 45, 55, ... .
את המספר 1 אין כוללים ברשימה, משום שהוא לא נחשב לראשוני. ראו מספר ראשוני להסבר בעניין זה.