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

מציאת כל המספרים הראשוניים בין 2 ל-120 באמצעות הנפה של ארטוסתנס, כשהסימון מתחיל ממספר בריבוע.

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

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

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

שיטת הנפה מתאימה לכל לוח כפל עד מספר כלשהו n, כאשר הגורמים הראשוניים אותם יש לבדוק הם עד לשורש n (טבעי). למשל, בלוח הכפל (המתואר בתמונה ) עד 120, יש לבדוק את חלוקת המספרים, עם הגורמים הראשוניים שהם עד לשורש 120 : 2 3 5 7 .

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


דוגמהעריכה

להלן פעולות האלגוריתם עבור המספרים עד 20.

  • רושמים את המספרים מ-2 ואילך, עד לגבול שקבענו מראש.
   2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
  • 2 הוא המספר הראשוני הראשון. סופרים מ-4 בצעדים של 2 ומסמנים את המספרים האלה:
     3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
       ^   ^   ^    ^     ^     ^     ^     ^     ^
   2
  • המספר הבלתי מסומן הראשון מעל 2 ברשימה הוא 3, המספר הראשוני הבא. סופרים מ-9 בצעדים של 3 ומסמנים:
       4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
       -   -   - ^  -    ^-     -  ^  -    ^-     -
   2 3 
  • המספר הבלתי מסומן הראשון מעל 3 ברשימה הוא 5. הספירה אמורה להתחיל מ-25 אך מספר זה גדול מ-20. לכן אנו מסיימים. המספרים הבלתי מסומנים ברשימה כעת הם הם כל המספרים הראשוניים מ-2 עד 20:
   2 3   5   7        11    13          17    19

הסימנים שסימנו במהלך הפעולה מהווים את הנפה שדרך החורים בה עוברים המספרים הראשוניים.

פסאודו קוד של נפת ארטוסתנסעריכה

algorithm Sieve of Eratosthenes is
    input: an integer n > 1.
    output: all prime numbers from 2 through n.

    let A be an array of Boolean values, indexed by integers 2 to n,
    initially all set to true.
    
    for i = 2, 3, 4, ..., not exceeding n do
        if A[i] is true
            for j = ,  + i,  + 2i,  + 3i, ..., not exceeding n do
                A[j] := false

    return all i such that A[i] is true.

קוד לנפת ארטוסתנס בשפת פייתוןעריכה

1 import math
2 
3 def all_primes(n):
4     lst = [True] * (n - 2)
5     for i in range(2, int(math.sqrt(n) + 1)):
6         if lst[i - 2]:
7             for j in range(i ** 2, n, i):
8                 lst[j - 2] = False
9     return [m + 2 for m in range(len(lst)) if lst[m]]

קישורים חיצונייםעריכה

  מדיה וקבצים בנושא הנפה של ארטוסתנס בוויקישיתוף