tolpp.com
yazılım ve programlama günlüğü

Sieve of Eratosthenes (Eratosthenes'in Eleği) Sep 27, 2012

Eratosthenes’in Eleği ya da diğer adıyla Eratosthenes’in Kalburu asal sayıların bulunması için kullanılan eski ve temel yöntemlerden biri.

Algoritma gerçekten bir elek mantığıyla çalışıyor. N sayısına kadar tüm asalları bulmak istediğimizde, en küçük asaldan başlayarak bu asalların tüm katları asal değil olarak işaretleniyor. N sayısına kadar tüm dizi dolaşıldığında asal değil olarak işaretlenmeyen tüm sayılar da asal oluyor.

Algoritmanın daha iyi anlaşılabilmesi ve görsel için :  (Vikipedi) Eratosten kalburu

Pseudocode :

Sieve(n)
//Eratosthenes'in Eleği'nin implementasyonu
//Input: n > 1 olan n tamsayısı
//Output: n'den küçük veya n e eşit asal sayılar dizisi
for p←2 to n do A[p]←p
for p←2 to floor(sqrt(n)) do
if A[p] != 0 //daha önceki döngü içerisinde p elenmemişse
j ← p ∗ p
while j ≤ n do
A[j]←0 //j. elemanı elenmiş olarak işaretle
j ←j + p
//A dizisindeki elenmemiş elemanları asal sayı olarak L dizisine at
i ←0
for p←2 to n do
if A[p] != 0
L[i]←A[p]
i ←i + 1
return L
Java :
public class Eratosthenes {
static int[] Sieve(int n) {
int[] A = new int[n + 1];
int[] L = new int[n + 1];
for (int p = 2; p < n; p++) A[p] = p; // ilk veriler atanıyor
for (int p = 2; p < (int) Math.sqrt(n); p++) {
if (A[p] != 0) {
int j = p * p;
while (j < n) { // asal sayının katları eleniyor
A[j] = 0;
j = j + p;
}
}
}
int i = 0;
for (int p = 2; p < n; p++) {
if (A[p] != 0) {
L[i] = A[p];
i++;
}
}
L = Arrays.copyOf(L, i);
return L;
}
}