תכנות — שיעור 44 22/January/2008    

חפוש ראשוניים

הצגנו את האלגוריתם הנפה של ארטוסתנס (המסננת) או (The Sieve of Eratosthenes ). באלגוריתם זה מתחילים עם רשימה שמאתחלים אותה בערכי אמת, ובכל שלב n מסמנים בשקר, את המקומות שאינם ראשוניים "בגלל" n . בקישורים, נמצא תיאור יותר מפורט מדויק וכן הדגמה חיה (בגירסא האנגלית!).

תרגילים

  1. כתבו תכנית שמממשת את האלגוריתם של ארטוסתנס. התכנית תדפיס את כל המספרים הראשוניים עד גבול עליון שניתן על-ידי המשתמש. לדוגמא:
    רמז: אפשר להתחיל את המסננת כך: 
    
M = int(sys.argv[1])
sieve = (M + 1)*[True]
    ולהתעלם מהאברים: 
    
sieve[0]
sieve[1]
חזרה לעמוד האם