Program wypisujący wszystkie liczby pierwsze
Spis Treści
1. Wstęp 4
2. Opis Algorytmu 4
3. Opis Kodu 4
4. Schemat Blokowy 7
5. Wymagania Programu 7
6. Zakończenie 8
Spis Listingów
Listing 1 5
Listing 2 6
Listing 3 6
Spis Schematów
Schemat 1 7
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ą.
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.
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) {
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.
.
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 **/
/** obliczamy pierwiastek liczby **/
/** ustawiamy na początku, że liczba jest liczbą pierwszą, ale potem spawdzimy czy napewno jest **/
/** pętla sprawdzająca czy wykorzystane liczby do sprawdzania są mniejsze do pierwiastka **/
/** sprawdzanie czy liczba jest podzielna przez jakąś liczbę **/
/** jeśli liczba się dzieli to ustawiamy, że nie jest liczbą pierwszą **/
/** jeśli liczba jest liczbą pierwszą to wypisujemy do pliku **/
Listing 3
I tak o to zapisany jest algorytm obliczający liczby pierwsze w języku java.
Schemat 1
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.
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
radek.br