Sieve of Eratosthenes
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.
Kesulitan 5/5 · 400 koin + bonus kecil pada penyelesaian pertama hari ini
Write primes_up_to(n) that returns every prime number from 2 ke n in order, using the sieve of Eratosthenes. primes_up_to(10) adalah [2, 3, 5, 7].
Klik Jalankan untuk melihat output di sini.