Lompat ke konten

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.

Masuk atau buat akun

IGCSE, A-Level & AP