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