Saringan Algoritma Eratosthenes: Python, C++ Example

Saringan Eratosthenes merupakan saringan bilangan prima yang paling sederhana. Ini merupakan algoritma bilangan prima untuk mencari semua bilangan prima dalam limit tertentu. Ada beberapa saringan bilangan prima. Misalnya- Saringan Eratosthenes, Saringan Atkin, Saringan Sundaram, dll.

Kata "saringan” artinya alat yang menyaring zat. Jadi, algoritma saringan di Python dan bahasa lain mengacu pada algoritma untuk menyaring bilangan prima.

Algoritma ini menyaring bilangan prima dengan pendekatan berulang. Proses penyaringan dimulai dengan bilangan prima terkecil. Bilangan prima adalah bilangan asli yang lebih besar dari 1 dan hanya memiliki dua pembagi, yaitu 1 dan bilangan itu sendiri. Bilangan yang bukan bilangan prima disebut bilangan komposit.

Dalam saringan metode Eratosthenes, bilangan prima kecil dipilih terlebih dahulu, dan semua kelipatannya disaring. Prosesnya berjalan berulang-ulang dalam rentang tertentu.

Sebagai contoh:

Mari kita ambil rentang angka dari 2 hingga 10.

Setelah menerapkan Saringan Eratosthenes, itu akan menghasilkan daftar bilangan prima 2, 3, 5, 7

Saringan Algoritma Eratosthenes

Berikut algoritma Saringan Eratosthenes:

Langkah 1) Buatlah daftar angka dari 2 hingga rentang n yang diberikan. Kita mulai dengan 2 karena merupakan angka prima pertama dan terkecil.

Langkah 2) Pilih angka terkecil pada daftar, x (awalnya x sama dengan 2), telusuri daftar tersebut, dan saring angka komposit yang sesuai dengan menandai semua kelipatan angka yang dipilih.

Langkah 3) Kemudian pilih bilangan prima berikutnya atau bilangan terkecil yang tidak diberi tanda pada daftar dan ulangi langkah 2.

Langkah 4) Ulangi langkah sebelumnya hingga nilai x lebih kecil atau sama dengan akar kuadrat dari n (x<=).

Catatan: Alasan matematisnya cukup sederhana. Kisaran bilangan n dapat difaktorkan sebagai-

n=a*b

Sekali lagi, n =*

= (faktor lebih kecil dari ) * (faktor lebih besar dari )

Jadi setidaknya salah satu darinya faktor utama atau keduanya harus <=. Jadi, melintasi ke akan cukup.

Langkah 5) Setelah keempat langkah tersebut, angka-angka tak bertanda yang tersisa akan menjadi semua bilangan prima pada rentang n yang diberikan.

Contoh:

Mari kita ambil contoh dan lihat cara kerjanya.

Untuk contoh ini, kita akan mencari daftar bilangan prima dari 2 hingga 25. Jadi, n=25.

Langkah 1) Pada langkah pertama, kita akan mengambil daftar angka dari 2 hingga 25 karena kita memilih n=25.

Langkah 2) Kemudian kita pilih angka terkecil pada daftar, x. Awalnya x=2 karena merupakan bilangan prima terkecil. Kemudian kita menelusuri daftar dan menandai kelipatan 2.

Kelipatan 2 untuk nilai n yang diberikan adalah: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24.

Catatan: Warna biru menunjukkan nomor yang dipilih, dan warna merah muda menunjukkan kelipatan yang dihilangkan

Langkah 3) Kemudian kita pilih bilangan terkecil berikutnya yang belum diberi tanda, yaitu 3, dan ulangi langkah terakhir dengan menandai kelipatan 3.

Langkah 4) Kami ulangi langkah 3 dengan cara yang sama sampai x= atau 5.

Langkah 5) Angka sisanya yang tidak diberi tanda adalah bilangan prima dari 2 sampai 25.

Kode Semu

Begin
	Declare a boolean array of size n and initialize it to true
	For all numbers i : from 2 to sqrt(n)
     		IF bool value of i is true THEN
         			i is prime
         			For all multiples of i (i<n)
             			mark multiples of i as composite
Print all unmarked numbers
End

Saringan Eratosthenes C/C++ Contoh kode

#include <iostream>
#include <cstring>
using namespace std;
void Sieve_Of_Eratosthenes(int n)
{
    // Create and initialize a boolean array
    bool primeNumber[n + 1];
    memset(primeNumber, true, sizeof(primeNumber));
    for (int j = 2; j * j <= n; j++) {
        if (primeNumber[j] == true) {
            // Update all multiples of i as false
            for (int k = j * j; k <= n; k += j)
                primeNumber[k] = false;
        }
    } 
    for (int i = 2; i <= n; i++)
        if (primeNumber[i])
            cout << i << " ";
}
int main()
{
    int n = 25;
    Sieve_Of_Eratosthenes(n);
    return 0;
}

Keluaran:

2 3 5 7 11 13 17 19 23

Saringan Eratosthenes Python Contoh Program

def SieveOfEratosthenes(n):
# Create a boolean array
	primeNumber = [True for i in range(n+2)]
	i = 2
	while (i * i <= n):
		if (primeNumber[i] == True):
			# Update all multiples of i as false
			for j in range(i * i, n+1, i):
				primeNumber[j] = False
		i += 1
	for i in range(2, n):
		if primeNumber[i]:
			print(i)
n = 25
SieveOfEratosthenes(n)

Keluaran:

Saringan Tersegmentasi

Kita telah melihat bahwa Saringan Eratosthenes diperlukan untuk menjalankan loop melalui seluruh rentang angka. Jadi, dibutuhkan ruang memori O(n) untuk menyimpan angka-angka tersebut. Situasinya menjadi rumit ketika kita mencoba menemukan bilangan prima dalam rentang yang sangat besar. Tidak mungkin untuk mengalokasikan ruang memori yang begitu besar untuk n yang lebih besar.

Algoritma ini dapat dioptimalkan dengan memperkenalkan beberapa fitur baru. Idenya adalah membagi rentang angka menjadi segmen yang lebih kecil dan menghitung bilangan prima dalam segmen tersebut satu per satu. Ini adalah cara yang efisien untuk mengurangi kompleksitas ruang. Metode ini disebut saringan tersegmentasi.

Optimasi dapat dicapai dengan cara berikut:

Gunakan saringan sederhana untuk mencari bilangan prima dari 2 sampai dan menyimpannya dalam array.
Bagilah rentang [0…n-1] menjadi beberapa segmen dengan ukuran paling banyak
Untuk setiap segmen, ulangi melalui segmen tersebut dan tandai kelipatan bilangan prima yang ditemukan pada langkah 1. Langkah ini memerlukan O() maksimal.

Saringan biasa memerlukan ruang memori tambahan O(n), sedangkan saringan tersegmentasi memerlukan O(), yang merupakan peningkatan besar untuk n yang besar. Metode ini juga memiliki kekurangan karena tidak meningkatkan kompleksitas waktu.

Analisis Kompleksitas

Kompleksitas Ruang:

Saringan sederhana algoritma eratosthenes membutuhkan ruang memori O(n). Dan saringan tersegmentasi membutuhkan
O() ruang tambahan.

Kompleksitas Waktu:

Kompleksitas waktu dari algoritma saringan eratosthenes reguler adalah O(n*log(log(n))). Alasan di balik kompleksitas ini dibahas di bawah ini.

Untuk bilangan n tertentu, waktu yang diperlukan untuk menandai bilangan komposit (yaitu, bilangan nonprima) adalah konstan. Jadi, jumlah kali loop dijalankan sama dengan-

n/2 + n/3 + n/5 + n/7 + ……∞

= n * (1/2 + 1/3 + 1/5 + 1/7 +…….∞)

Perkembangan harmonik dari jumlah bilangan prima dapat dikurangkan sebagai log(log(n)).

(1/2 + 1/3 + 1/5 + 1/7 +…….∞) = log(log(n))

Jadi, kompleksitas waktunya akan menjadi-

T(n) = n * (1/2 + 1/3 + 1/5 + 1/7 + ……∞)

= n * catatan(catatan(n))

Oleh karena itu kompleksitas waktunya adalah O(n * log(log(n)))

Selanjutnya, Anda akan mempelajari tentang Segitiga Pascal

Ringkasan

Saringan Eratosthenes menyaring bilangan prima dalam batas atas tertentu.
Pemfilteran suatu bilangan prima dimulai dari bilangan prima terkecil yaitu “2”. Hal ini dilakukan secara berulang.
Iterasi dilakukan hingga akar kuadrat dari n, dimana n adalah rentang bilangan yang diberikan.
Setelah perulangan tersebut, bilangan yang tersisa adalah bilangan prima.