Sieve of Eratosthenes · Saringan 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.
Sieve of Eratosthenes
Ahli matematika Yunani Eratosthenes menemukan bilangan prima tanpa membagi apa pun: tuliskan angka-angkanya, lalu coret kelipatan dari setiap bilangan prima.
[True] * (n + 1) membuat daftar n + 1 nilai True, satu untuk setiap angka dari 0 hingga n. Tandai 0 dan 1 sebagai bukan prima. Kemudian, untuk setiap p yang masih ditandai True, set setiap kelipatan dari p mulai dari p * p ke arah atas menjadi False. Angka-angka yang masih ditandai True di akhir adalah bilangan prima.
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]. · Tulis primes_up_to(n) yang mengembalikan setiap bilangan prima dari 2 hingga n secara berurutan, menggunakan saringan Eratosthenes. primes_up_to(10) adalah [2, 3, 5, 7].
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.