Sieve of Eratosthenes · מסננת ארסטוסתנס
Sieve of Eratosthenes
The Greek mathematician Eratosthenes found primes without dividing anything: write down the numbers, then cross out the multiples of each prime.
[True] * (n + 1) makes a list of n + 1 True values, one for each number from 0 to n. Mark 0 and 1 as not prime. Then, for each p still marked True, set every multiple of p from p * p onwards to False. The numbers still marked True at the end are the primes.
מסנן ארטוסטנס
המתמטיקאי היווני ארטוסטנס מצא מספרים ראשוניים ללא חלוקה: כתיבת המספרים, ואז השבת קווים על כפולים של כל מספר ראשוני.
[True] * (n + 1) יוצר רשימה של n + 1 True ערכים, אחד לכל מספר מ0 עד n. סימון 0 ו1 כלא ראשוניים. לאחר מכן, עבור כל p שעדיין מסומן כTrue, נגדיר כל כפול של p החל מp * p לFalse. המספרים שעדיין מסומנים כTrue בסוף הם המספרים הראשוניים.
Write primes_up_to(n) that returns every prime number from 2 to n in order, using the sieve of Eratosthenes. primes_up_to(10) is [2, 3, 5, 7]. · כתוב primes_up_to(n) שמחזיר כל המספרים הראשוניים מ-2 ועד n בסדר, בעזרת מסננת ארסטוסתנס. primes_up_to(10) הוא [2, 3, 5, 7].
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.