MathPemulaFase C–FE1E5

PRIME SIEVE

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.

Example use case

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

Syllabus

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

Objectives

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

How It Works

·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

Prerequisites

·Bilangan prima
·Kelipatan

Real-World Uses

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

Complexity O(n log log n)