Sito Eratostenesa

Liczby pierwsze

Zgodnie z obietnicą, dziś przedstawię optymalny algorytm do przeglądania liczb pierwszych. Algorytmem tym jest oczywiście sito Eratostenesa. Sam program napisany został w języku Java. Algorytm ten jest optymalny, tzn. angażuje minimum czasu programisty i mocy obliczeniowej komputera, więc jest to bardzo pozytywny aspekt jego działania. Staje też – niejako w opozycji – do programu, który przedstawiony został w tym wpisie.

Działanie algorytmu polega na wykreślaniu kolejnych wielokrotności od 2 do pierwiastka z danej liczby, zgodnie z animacją (liczby pierwsze przedstawione zostały kolorem ciemno-szarym):

Sito Eratostenesa

Rys. 1. Sito Eratostenesa (cyberhub.pl)

Jeśli chodzi o aspekt techniczny, to aplikacja na wejściu pobiera od użytkownika zakres (badany przedział) w postaci wartości dolnej i górnej:

[code language="java"]
Scanner input = new Scanner(System.in);

System.out.println("Podaj dolną wartość przedziału: ");
int num0 = input.nextInt();

System.out.println("Podaj górną wartość przedziału: ");
int num = input.nextInt();
[/code]

Na początku utworzona zostaje tablica typu logicznego (boolean) i nadany zostaje jej rozmiar num + 1, tak aby ustrzec się przed błędem przekroczenia jej zakresu (ArrayIndexOutBoundsException):

[sourcecode language="java"]
boolean b[] = new boolean[num + 1];
[/sourcecode]

Dlaczego tablica boolean? Ano dlatego, że liczby złożone będą w niej zapisywane jako wartość logiczna true, natomiast pierwsze jako false.

Następnym punktem jest utworzenie pętli, której zadaniem jest przeglądanie liczb w zakresie od 2 do \(\sqrt{num}\), oraz badanie (przy pomocy zagnieżdżonej pętli for) ich wielokrotności, oczywiście nieprzekraczających wartości num. Badanie to spowoduje wykreślanie (b[j] = true) powstałych w ten sposób liczb złożonych z tablicy (w rzeczywistości niejawne podstawianie w pozostałe miejsca wartości false). W momencie napotkania liczby złożonej w zakresie do \(\sqrt{num}\), program przechodzi do następnej liczby, dzięki instrukcji continue:

[code lang="java"]
for (i = 2; i <= Math.sqrt(num); i++) {
if (b[i] == true)
continue;
for (int j = 2 * i; j <= num; j += i)
b[j] = true;
}
[/code]

Na końcu pozostaje tylko wypisać znalezione w ten sposób liczby pierwsze wraz z ich liczbą:

[code lang="java"]
for (i = num0; i <= num; i++)
if (b[i] == false) {
System.out.println(i);
counter++;
}

System.out.println("Znaleziono " + counter + " liczb pierwszych.");
[/code]

Całość przedstawia się następująco:

[code lang="java"]
import java.util.Scanner;

public class Zad3SitoEratostenesa {

public static void main(String[] args) {
Scanner input = new Scanner(System.in);

System.out.println("Podaj dolną wartość przedziału: ");
int num0 = input.nextInt();

System.out.println("Podaj górną wartość przedziału: ");
int num = input.nextInt();
boolean b[] = new boolean[num + 1];
int i, counter = 0;

for (i = 2; i <= Math.sqrt(num); i++) {
if (b[i] == true)
continue;
for (int j = 2 * i; j <= num; j += i)
b[j] = true;
}

for (i = num0; i <= num; i++)
if (b[i] == false) {
System.out.println(i);
counter++;
}
System.out.println("Znaleziono " + counter + " liczb pierwszych.");
}
}
[/code]

Zostaw odpowiedź

Twój email nie zostanie opublikowany. Pola wymagane oznaczone *