Eratosthenovo síto

Zadání

Nalezněte prvočísla v zadaném intervalu pomocí Eratosthenova síta.




Teorie

Prvočíslo je takové číslo, které je dělitelné pouze jedničkou a samo sebou (bavíme se o přirozených číslech a dělení beze zbytku).
Eratosthenovo síto je metoda, která postupně prochází přirozená čísla a vyhazuje z následující posloupnosti násobky aktuálního prvočísla - například u čísla 3 se z následujících čísel vyhází všechny násobky čísla 3, tedy 6, 9, 12, 15 atd. Pokračuje se na další číslo, které stále nebylo touto metodou vyřazeno. Na anglické wikipedii je k tomu pěkný obrázek.

Řešení

Kód tohoto programu bude velice jednoduchý, proto ho téměř celý vpíšeme do hlavní metody. Začneme načtením intervalu pomocí Scanneru:

Scanner sc = new Scanner(System.in);
System.out.println("Zadejte interval:");
int number = sc.nextInt();

Dále si nainicializujeme pole, které bude obsahovat prvočísla. Do každého prvku pole vložíme hodnotu jeho indexu pro pozdější snazší výpis pole. Vyřazené prvky budou mít hodnotu -1.

int[] primes = new int[number];
if(number <= 2)System.exit(-1);
for(int i = 0; i < number; i++)
    primes[i] = i;
primes[0] = -1;
primes[1] = -1;
primes[2] = 2;

Následující cyklus vždy vezme první prvek, který nemá hodnotu -1, a vyřadí z pole všechny jeho násobky. Hlavní cyklus proměnnou i neinkrementuje, ale zvyšuje vždy o dva, protože víme, že sudé prvočíslo bude pouze číslo 2.

for(int i = 3; i < number; i += 2){
    if(primes[i] == -1)continue;
    for(int j = 1; i + j * i < number; j++)
        primes[i + j * i] = -1;
}

Pro výpis prvočísel stačí napsat jedoduchou metodu, ale výpis větších polí prvočísel může program o hodně zpomalit (lepší je třeba metodu upravit a vypsat si jen posledních pár).
Metoda může vypadat třeba takto:

public static void writePrimes(int[] p){
    int d = p.length;
    String pp = "";
    pp += p[2] + ",";
    for(int i = 3; i < d; i+=2)
        if(p[i]>1)
            pp += p[i] + ",";
    System.out.println(pp);
}

Pokud se spokojíme s pomalejším výpisem, který ale bude postupný, nemusíme celou posloupnost vkládat do zvláštní proměnné, ale můžeme použít metody System.out.print(), výpis bude ale o dost pomalejší.

Pokud vás ještě zajímá, jak dlouho program běží, můžete po načtení intervalu načíst aktuální čas v milisekundách pomocí metody System.currentTimeMillis() a na konci programu vypsat rozdíl aktuálního času a času uloženého při načtení intervalu.