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 :
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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 |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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; | |
| } | |
| } |
