Algoritma dan Pemrograman untuk Mencari Bilangan Prima: Studi Kasus 1-100
4 (333 suara) Menemukan bilangan prima adalah masalah klasik dalam matematika dan ilmu komputer. Sebuah bilangan prima (atau prima) adalah bilangan asli yang lebih besar dari 1 dan tidak memiliki pembagi selain 1 dan dirinya sendiri. Bilangan prima pertama adalah 2, 3, 5, 7, 11, dan seterusnya. Bilangan prima sangat penting dalam teori bilangan dan kriptografi.
Memahami Bilangan Prima
Untuk menentukan bilangan prima, kita perlu memahami konsep pembagian. Suatu bilangan dikatakan prima jika hanya habis dibagi 1 dan dirinya sendiri. Misalnya, 7 adalah bilangan prima karena hanya habis dibagi 1 dan 7. Di sisi lain, 6 bukanlah bilangan prima karena habis dibagi 1, 2, 3, dan 6.
Algoritma untuk Menemukan Bilangan Prima
Ada banyak algoritma untuk menemukan bilangan prima. Salah satu algoritma yang paling sederhana dan paling terkenal adalah algoritma _naive_. Algoritma ini bekerja dengan memeriksa setiap bilangan bulat dari 2 hingga akar kuadrat dari bilangan input. Untuk setiap bilangan bulat, algoritma memeriksa apakah bilangan bulat tersebut habis dibagi bilangan input. Jika bilangan input habis dibagi bilangan bulat, maka bilangan input tersebut bukanlah bilangan prima. Jika tidak, bilangan input adalah bilangan prima.
Algoritma lain yang lebih efisien disebut Saringan Eratosthenes. Algoritma ini bekerja dengan membuat daftar semua bilangan bulat dari 2 hingga bilangan input. Kemudian, algoritma secara berulang menandai kelipatan dari setiap bilangan prima sebagai non-prima, dimulai dari 2. Bilangan pertama yang tidak ditandai adalah bilangan prima.
Menerapkan Algoritma dalam Kode
Mari kita terapkan algoritma _naive_ dan Saringan Eratosthenes dalam Python untuk menemukan semua bilangan prima antara 1 dan 100.
Algoritma _Naive_
```python
def is_prima(n):
"""Mengembalikan True jika n adalah bilangan prima, False jika tidak."""
if n <= 1:
return False
for i in range(2, int(n0.5) + 1):
if n % i == 0:
return False
return True
prima = []
for i in range(2, 101):
if is_prima(i):
prima.append(i)
print("Bilangan prima antara 1 dan 100 adalah:", prima)
```
Saringan Eratosthenes**
```python
def saringan_eratosthenes(n):
"""Mengembalikan daftar semua bilangan prima yang lebih kecil atau sama dengan n."""
prima = [True] * (n + 1)
p = 2
while (p * p) <= n:
if prima[p] == True:
for i in range(p * p, n + 1, p):
prima[i] = False
p += 1
prima_numbers = []
for p in range(2, n + 1):
if prima[p]:
prima_numbers.append(p)
return prima_numbers
prima = saringan_eratosthenes(100)
print("Bilangan prima antara 1 dan 100 adalah:", prima)
```
Kedua program akan mencetak daftar bilangan prima yang sama: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97].
Kesimpulan
Menemukan bilangan prima adalah tugas mendasar dalam ilmu komputer dengan berbagai aplikasi. Algoritma _naive_ menyediakan pendekatan langsung, sedangkan Saringan Eratosthenes menawarkan metode yang lebih efisien, terutama untuk bilangan yang lebih besar. Memahami algoritma ini memungkinkan kita untuk mengidentifikasi bilangan prima secara efisien, yang selanjutnya dapat digunakan dalam berbagai domain seperti kriptografi dan analisis data.
