MatematikaPemulaFase C–FE1E5

Saringan Bilangan Prima

Prime Sieve (Saringan Eratosthenes) mencari semua bilangan prima hingga n dengan menandai kelipatan setiap bilangan prima sebagai bukan prima. Mulai dari p=2, semua kelipatannya dicoret, lalu lanjut ke bilangan berikutnya yang belum tercoret. Visualisasi memperlihatkan angka-angka yang dicoret (tanda X) satu per satu hingga hanya bilangan prima yang tersisa.

Contoh kasus

Menghasilkan tabel bilangan prima untuk pembangkitan kunci awal pada eksperimen kriptografi RSA.

Silabus

Menemukan semua bilangan prima sampai n dengan mencoret kelipatan tiap prima, menyisakan angka yang tak pernah tercoret.

Tujuan Belajar

·Memahami cara menandai kelipatan sebagai bukan prima
·Menjelaskan mengapa angka tersisa pasti bilangan prima
·Menerapkan saringan untuk membangkitkan daftar prima

Cara Kerja

·Tulis semua angka dari 2 sampai n
·Mulai dari 2, coret semua kelipatannya
·Lanjut ke angka berikutnya yang belum tercoret (3, lalu 5, ...)
·Coret semua kelipatan angka prima itu juga
·Angka yang tersisa tanpa coretan adalah bilangan prima

Prasyarat

·Bilangan prima
·Kelipatan

Contoh Nyata

·Menyiapkan bilangan prima besar untuk kunci kriptografi RSA
·Membuat tabel prima untuk soal-soal lomba pemrograman

Kompleksitas O(n log log n)