Cek Bilangan Prima dan Faktorisasi Prima

Bilangan prima adalah bilangan asli lebih dari 1 yang tidak memiliki pembagi positif selain 1 dan dirinya sendiri. Bilangan prima pertama adalah 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... 2 adalah satu-satunya bilangan prima genap: setiap bilangan genap lainnya habis dibagi 2, sehingga merupakan bilangan komposit. Inilah yang membuat 2 unik di antara bilangan prima. Cara mengecek apakah sebuah bilangan prima: cukup periksa apakah bilangan itu habis dibagi bilangan prima hingga akar kuadratnya. Untuk menguji 97, periksa 2, 3, 5, dan 7 (√97 ≈ 9,8). Jika tidak ada yang membaginya habis, bilangan itu prima. Bilangan prima tak terhingga banyaknya: Euclid membuktikannya sekitar tahun 300 SM. Bilangan prima terbesar yang diketahui (per 2024) memiliki lebih dari 40 juta digit. Mengapa bilangan prima penting: enkripsi RSA (yang mengamankan internet banking, email, dan HTTPS) bergantung pada fakta bahwa mengalikan dua bilangan prima besar itu mudah, tetapi menguraikan hasilnya kembali menjadi faktor-faktor prima secara komputasi hampir mustahil.