Program wypisujący wszystkie liczby pierwsze

Spis Treści

Spis Listingów

Spis Schematów

1. Wstęp

Liczby pierwsze są to takie liczby naturalne, które większe są od jedynki i podzielne bez reszty przez samą siebie i jedynkę. Jednym z pytań dotyczących liczb pierwszych, które narzuca się każdemu jest pytanie o liczbę tych liczb: ile ich jest, skończenie wiele czy, wręcz przeciwnie, nieskończenie? Na to akurat znamy odpowiedź od czasów starożytnych: liczb pierwszych jest nieskończenie wiele. Wiedział o tym już w IV w. p.n.e. sam wielki Euklides. Innymi słowy, nie istnieje największa liczba pierwsza: dla każdej danej liczby pierwszej możemy znaleźć większą. Istotnie, gdyby była jedynie skończona liczba liczb pierwszych (np. P) to iloczyn wszystkich tych P liczb, zwiększony o jedynkę, musiałby być też pierwszy, bo przy dzieleniu przez którąkolwiek z tych P liczb dawałby oczywiście resztę jeden); zatem przypuszczenie, że jest ich P, jest fałszywe, bowiem znaleźliśmy oto następną.

2. Opis Algorytmu

Ta dość prosta konstrukcja daje również teoretycznie przepis na konstruowanie coraz większych liczb. Np. 2*3*5+1=31; 31 jest liczbą pierwszą. Nietrudno spostrzec, że ten przepis ma też wady. Nie można nim otrzymać np.: 11,13,17,19,..., ale za to stosując wzór 2*3*3-1=17, uda się otrzymać właśnie takie liczby. Te dwa wzory nie są doskonałe, gdyż nawet stosując je, otrzymamy liczby nie pierwsze. Więc musimy jeszcze sprawdzić czy dana liczba na pewno jest liczbą pierwszą. Najpierw obliczamy pierwiastek obliczonej liczby. Następnie liczbę wyznaczoną ze wzoru sprawdzamy czy się dzieli przez liczby z przedziału od 2 do jej pierwiastka ( do pierwiastka, ponieważ liczba większa od pierwiastka na pewno nie będzie dzielić tej liczby, np. pierwiastek liczby 4 to 2, więc dzieląc 4 przez 3 wynik będzie ułamkiem z przedziału 0 do 1). Jeśli warunek nie będzie spełniony, tzn. liczba nie będzie się dzielić przez dane liczby to na pewno jest liczbą pierwszą. Czyli ogólnie rzecz biorąc będą wykorzystywane wzory: 6*n-1 i 6*n+1. Te wzory pozwalają na ominięcie wielu zbędnych liczb do zbadania.

3. Opis Kodu

A o to przykładowy kod (Lst. 1), który pozwala na wyznaczanie liczb pierwszych.

import java.io.*;

public class Pi_Li {

static String File = "Data.txt";

public static void main(String[] args) throws IOException{

PrintWriter out = new PrintWriter(

new File(File).getAbsoluteFile());

int a = 2, e, f, g = 0, h = -1, i = 1;

double b;

boolean c;

while(0 < 1)

{

if (g < 2){

out.println(a);

g++;

a++;

}

else

{

a = 6 * i + h;

b = Math.floor(Math.sqrt(a));

f = 2;

c = true;

while(f <= b) {

e = a % f++;

if (e==0) c=false;

}

if (c) {

out.println(a);

g++;

}

h = -h;

if(h == -1) i++;

}

}

}

}

Listing 1

Program wyliczający liczby pierwsze będzie zapisywał wynik do pliku txt, więc najpierw musimy nazwać nasz plik (Data.txt). Następnie musimy dodać obsługę błędu, tzn. by w czasie zapisywania do pliku nie wyskakiwały nam błędy, do tego celu używamy procedury trows IOException. Potem tworzymy nowy obiekt, który będzie miał na celu zapisywanie do pliku o nazwie Data.txt.

static String File = "Data.txt";

public static void main(String[] args) throws IOException{

PrintWriter out = new PrintWriter(

new File(File).getAbsoluteFile());

.

.

.

}

Listing 2

Żeby wypisywał do nieskończoności liczby pierwsze, musimy utworzyć pętle, która będzie działać właśnie do nieskończoności ( while(0 < 1) ) . Następnie właśnie tworzymy kod algorytmu, który będzie nam obliczał liczby pierwsze.

/** wzór 6*n-1 lub 6*n+1 **/

a = 6 * i + h;

/** obliczamy pierwiastek liczby **/

b = Math.floor(Math.sqrt(a));

f = 2;

/** ustawiamy na początku, że liczba jest liczbą pierwszą, ale potem spawdzimy czy napewno jest **/

c = true;

/** pętla sprawdzająca czy wykorzystane liczby do sprawdzania są mniejsze do pierwiastka **/

while(f <= b) {

/** sprawdzanie czy liczba jest podzielna przez jakąś liczbę **/

e = a % f++;

/** jeśli liczba się dzieli to ustawiamy, że nie jest liczbą pierwszą **/

if (e==0) c=false;

}

/** jeśli liczba jest liczbą pierwszą to wypisujemy do pliku **/

if (c) {

out.println(a);

g++;

}

h = -h;

if(h == -1) i++;

Listing 3

I tak o to zapisany jest algorytm obliczający liczby pierwsze w języku java.

4. Schemat Blokowy

Schemat 1

5. Wymagania Programu

Program wymaga zainstalowanego na komputerze środowiska java environment. Bez tego program nie uruchomi się. Przydałby się jeszcze komputer z dużą ilością Hz, jeśli użytkownik chce by wyniki szybko były obliczane. Przy małej ilości i przy dłuższej pracy programu, duże prawdopodobieństwo jest, że komputer może się zawiesić i przestać odpowiadać, gdyż obliczenia będą na bardzo wysokich liczbach.

6. Zakończenie

I tak o to został przedstawiony jeden ze sposobów na wyznaczanie liczb pierwszych. Tak naprawdę algorytmów, które pozwolą na wyznaczenie liczb pierwszych jest bardzo dużo. Do dzisiaj nie znamy ostatniej liczby pierwszej, jeśli taka w ogóle istnieje. Ciągle trwają pracę nad obliczeniem ostatniej liczby pierwszej, ale zawsze znajduje się większą liczbę pierwszą od tej. Stosuje się superkomputery do obliczania największej liczby pierwszej, ale i one nie są w stanie obliczyć „ostatniej”.

9

START

0 < 1

file ← Data.txt

a ← 2

g ← 0

h ← - 1

i ← 1

g < 2

Pisz a

g ← g + 1

a ← a + 1

a ← 6 * i + h

b ← √a

f ← 2

c ← true

f <= b

e ← a mod f

f ← f + 1

e = 0

c ← false

c

Pisz a

g ← g + 1

h ← - h

h = -1

i ← i + 1

tak

nie

tak

tak

nie

tak

nie

tak

nie

tak

nie

---