הנפה של ארטוסתנס – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
כלום |
מ הגהה |
||
שורה 3:
[[קובץ:Sieve_of_Eratosthenes_animation.gif|שמאל|ממוסגר|מציאת כל המספרים הראשוניים בין 2 ל-120 באמצעות הנפה של ארטוסתנס, כשהסימון מתחיל ממספר בריבוע.]]
ב[[תורת המספרים]], '''ה[[מסננת|נפה]] של ארטוסתנס''' הוא [[אלגוריתם]] פשוט למציאת כל ה[[מספר ראשוני|מספרים הראשוניים]] עד ל[[מספר שלם]] מסוים. הנפה הומצאה על ידי המתמטיקאי היווני [[ארטוסתנס
מתחילים עם רשימת כל המספרים השלמים מ-2 ועד המספר הנבחר. בכל שלב, המספר הקטן ביותר ברשימה שעוד לא טופל מוכרז כראשוני, וכל הכפולות שלו (שהן [[מספר פריק|מספרים פריקים]]) מסומנות בתוך הרשימה. בסופו של דבר כל המספרים ברשימה שלא סומנו הם המספרים הראשוניים.
| |||