Liczby pierwsze w programowaniu

Liczby pierwsze

W tym poście postaramy się przybliżyć algorytm, oraz napisać program w Java, którego zadaniem będzie wyszukiwanie wszystkich liczb pierwszych z danego przedziału. Oprócz tego, program wypisywał będzie również i liczby złożone, wraz ze wszystkimi dzielnikami, posortowanymi rosnąco, oraz odstępy pomiędzy kolejnymi primes. Zadanie to – oprócz poniższego kodu – można sobie również ściągnąć ze źródłowej paczki src.zip, w której zawarte są wszystkie programy napisanego kursu programowania w języku Java.

Na początku należy zaznaczyć, że optymalnym algorytmem pierwszeństwa jest sito Eratostenesa, jednak w omawianym przypadku (poszukujemy jeszcze liczby złożone wraz z ich dzielnikami, oraz odstępem pomiędzy kolejnymi liczbami pierwszymi), nie będzie on spełniał swojej roli.

O fenomenie liczb pierwszych, oraz o frapującej i związanej z nimi hipotezie Riemanna, napiszę w innym poście, tymczasem zadajmy sobie pytanie: czym w ogóle jest liczba pierwsza? Otóż jest to liczba, która ma dokładnie 2 dzielniki: 1 i samą siebie. Liczby pierwsze są cegiełkami, atomami, z iloczynów których zbudowane są wszystkie inne liczby.
Jedynie 0 i 1 nie są ani liczbami pierwszymi ani złożonymi, natomiast najmniejszą liczbą pierwszą (i jednocześnie jedyną parzystą) jest liczba 2. Co bardziej dociekliwy czytelnik może przy okazji zadać pytanie dlaczego liczba 1 nie jest pierwsza. Otóż jest to umowa, bowiem korzystamy tutaj z podstawowego twierdzenia arytmetyki, które mówi o tym, że liczby złożone dają się przedstawić jednoznacznie w postaci iloczynu liczb pierwszych. Gdyby jednak jedynka była pierwsza, nie moglibyśmy mówić o jednoznaczności. Czy iloczyn liczb 1 × 1 × 3 × 2 × 7 jest identyczny z iloczynem 1 × 3 × 2 × 7? Odpowiedź brzmi: tak; ale uzyskane są w sposób niejednoznaczny. Posiłkując się powyższą wiedzą teoretyczną, przejdźmy zatem do konkretów.

Na początku działania programu wypadałoby przyjąć sobie jakiś badany zakres liczb i zawrzeć go w pętli. Potrzebna będzie wartość startowa i końcowa badanego przedziału liczb, a badanie zaczynamy od dwójki, zatem i \(\neq\) 0 \(\wedge\) i \(\neq 1\):

for (i = 2; i <= 1000000; i++) {
}

Następnie musimy określić, jakie dzielniki każdej kolejnej inkrementowanej liczby (i), będziemy badać. Najprostszą sytuacją jest przypadek, w którym będziemy badać wszystkie dzielniki danej liczby począwszy od 2 aż do i. Byłoby to jednak zbytnie uproszczenie, które pozwoliłoby nam – dla coraz większych liczb – na robienie sobie coraz bardziej długich przerw w oczekiwaniu na wyniki, a nasz komputer skazałoby na nie lada wysiłek. Pomyślmy tylko ile czasu zajęłoby dzielenie każdej z liczb powyższego zakresu (od 2 do miliona) przez dzielniki: począwszy od dwójki aż do owej liczby! Przez to nasz algorytm nie będzie więc optymalny.

Istnieje jednak rozwiązanie zgoła lepsze od przedstawionego powyżej: otóż można przecież badać dzielniki od 2 do \(\sqrt{i}\).

Bystry czytelnik zauważy jednak, iż pierwiastki z liczb: 2, oraz 3 nie są liczbami naturalnymi, ale rzeczywistymi:

$$\sqrt{2}\approx1,4$$

$$\sqrt{3}\approx1,7$$

Specjalnie dla tych dwóch przypadków musimy więc uwzględniać liczbę o jeden większą od \(\sqrt{i}\), tak aby liczby te uznane zostały przez program jako pierwsze. Mamy więc:

st = (int) Math.sqrt(i);

oraz:

for (j = 2; j <= st + 1; j++) {
}

Jak już wspomniano liczba jest złożona wtedy gdy dzieli się, oprócz 1 i samej siebie, przez jakąś inną liczbę z resztą równą 0. Z tego względu, aby mieć pewność, że oto otrzymaliśmy liczbę złożoną wystarczy w powyższej pętli for badać warunek:

if (i % j == 0 && i != 2) {

}

Jeśli wartość logiczna tej instrukcji jest typu true, to możemy wypisać komunikat, że znaleźliśmy liczbę złożoną. Warto jednak wprowadzić wcześniej licznik znalezionych dzielników (countDivs). Gdy tego nie zrobimy, wtedy z każdym znalezionym dzielnikiem program będzie wypisywał, że liczba jest złożona, a tego chcielibyśmy uniknąć. Wystarczy jeden taki komunikat – tylko przy pierwszym znalezionym dzielniku:

countDivs++;
if (countDivs == 1)
System.out.print(": złożona. Dzielniki: ");

No dobrze – powie czytelnik – ale w ten sposób znajdziemy małe dzielniki (tylko do \(\sqrt{i} + 1\)), a co z dużymi? Weźmy na przykład liczbę 400. Pierwiastek z tej liczby wynosi 20. Znajdziemy więc jeden z małych dzielników, np. ten równy 5, 10 czy 20, a co z większymi: 80, 100 lub 200? Odpowiedź jest następująca: znajdując mały dzielnik, znajdujemy również ten duży! Problem tylko w tym, że trzeba go jeszcze jakoś wypisać. Nie możemy skorzystać z operacji modulo zdefiniowanej powyżej, ponieważ otrzymujemy dzięki niej tylko j, a potrzebujemy jeszcze drugiego dzielnika: tego większego. Rozwiązaniem jest tutaj użycie zwykłego dzielenia. W ten sposób otrzymamy 2 dzielniki. Wiemy przecież, że skoro otrzymaliśmy liczbę złożoną i przeglądamy mały dzielnik tej liczby, to dzieląc tą liczbę przez mały dzielnik, otrzymujemy dzielnik większy (b). Innymi słowy reszta z dzielenia liczby przez mały dzielnik równa jest 0. Stąd do powyższej instrukcji warunkowej dochodzi kod:

b = i / j;

Teraz najciekawsze: jak wypisywać dzielniki? Niestety wypisywanie w każdej iteracji pętli for obu zmiennych: j i b jest zadaniem tylko z pozoru rozwiązującym problem, bowiem dzielniki te będą co prawda wypisywane, ale nieelegancko, tzn. nierosnąco. Dodatkowo będą się powtarzać ;-( A może wypisywać je w tablicy, którą dodatkowo sortować?! Nic bardziej mylnego, tablic można by użyć, gdybyśmy wiedzieli z góry jaki będzie jej rozmiar. Tutaj rozmiar takiej tablicy z każdą iteracją pętli for się zmienia, więc uśmiech na naszej twarzy musi ustąpić grymasowi niezadowolenia ?? Kolejnym rozwiązaniem jest lista interfejsu List. Doskonale! – krzyknie programista. Niestety… Tutaj również początkowy zachwyt musi ulec ostudzeniu i dokładnemu przeanalizowaniu dlaczego i to rozwiązanie jest niezbyt dobre. Wprawdzie interfejs List umożliwia dynamiczną zmianę swego rozmiaru, a nawet sortowanie danych poprzez statyczną metodę sort() klasy Collections, jednak nie umożliwia prostego usuwania duplikatów.

Złotym skarbem wyciągniętym spośród artefaktów skrzyni różności okazuje się być dopiero połączenie interfejsu List z innym interfejsem: Set. Ten ostatni ma – z naszego punktu widzenia – również wadę (nie umożliwia sortowania: metoda sort() „na nim” nie działa), ale połączenie go z interfejsem List przyniesie oczekiwane rezultaty.

Na początku programu należy więc zadeklarować najpierw List (o nazwie dividers), następnie Set (o nazwie hs), a następnie dodać – za pomocą metody addAll(), listę dividers do seta hs. W kroku następnym usuwamy duplikaty z dodanej do hs listy dividers metodą clear() i dodajemy z powrotem hs do dividers, aby móc go później sortować. Tak oto poradziliśmy z problemem, który na początku wydawał się nie do przeskoczenia ? Całość tego fragmentu wygląda następująco:

List<Integer> dividers = new ArrayList<Integer>();
Set<Integer> hs = new HashSet<>();
hs.addAll(dividers);
dividers.clear();
dividers.addAll(hs);

Teraz wystarczy – przy pętli dzielników i instrukcji warunkowej liczby złożonej – dodawać za każdym razem do hs nasze dzielniki:

hs.add(j);
hs.add(b);

To jeszcze nie koniec tego fragmentu programu. Nie wystarczy przecież usunąć same duplikaty, ale – jak zostało wyżej wspomniane – musimy je jeszcze posortować. Robimy to oczywiście na końcu – po zbadaniu wszystkich dzielników danej liczby – czyli w praktyce po osiągnięciu wartości \(\sqrt{i}+1\), oraz przy założeniu, że znaleziono przynajmniej jeden dzielnik (co oznacza, że badana aktualnie liczba nie jest pierwsza):

if (j == st + 1 && countDivs >= 1) {
List sortedList = new ArrayList(hs);
Collections.sort(sortedList);
System.out.print(sortedList);
}

Przy tak skonstruowanym wyszukiwaniu liczb złożonych, oraz ich dzielników, poinformowanie o znalezieniu liczby pierwszej wydaje się być już tylko formalnością (kod poniżej). Ponadto warto jeszcze wprowadzić kilka linijek kodu, odpowiedzialnych za obliczanie odstępu (distance), jaki dzieli 2 kolejne liczby pierwsze. Uzyskamy go odejmując od aktualnej liczby pierwszej (i), poprzednią (k). Oczywiście – po wykonywaniu odejmowania – aktualna liczba pierwsza staje się poprzednią dla następnej iteracji (k = i):

if (j == st + 1 && countDivs == 0) {
System.out.print(": PIERWSZA ");
countPrime++;

if (i == 2)
distance = 0;
else
distance = i - k;
System.out.print(" Odstęp: " + (distance));
k = i;
}

Jak widać zliczamy również ich ilość w badanym przedziale za pomocą zmiennej countPrime.

Zanim przejdziemy do następnej badanej za pomocą pętli for liczby – czyścimy hs, oraz – koniecznie – zerujemy licznik dzielników, dodając także nową linię:

countDivs = 0;
hs.clear();
System.out.println();

Na końcu pozostaje nam zbadać za pomocą statycznej metody currentTimeMillis() klasy System, ile trwało wyszukiwanie liczb pierwszych oraz złożonych wraz z ich dzielnikami:

t1 = System.currentTimeMillis();
t = t1 - t0;</pre>
System.out.println("\nZnalezionych liczb pierwszych: " + countPrime + ", w czasie: " + t + " ms" + " (" + t * 0.001 + " s).");

przy czym:

long t0 = System.currentTimeMillis(), t1, t;

Zmienne powyższe zadeklarowane są na początku programu. Całość przedstawia się następująco:

// Copyright by cyberhub.pl

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Zad3LiczbyPiZlo {
public static void main(String[] args) {
int i, j, b, st, countPrime = 0, countDivs = 0, k = 0, distance;
long t0 = System.currentTimeMillis(), t1, t;
float st2;
List<Integer> dividers = new ArrayList<Integer>();
Set<Integer> hs = new HashSet<>();
hs.addAll(dividers);
dividers.clear();
dividers.addAll(hs);

for (i = 2; i <= 100; i++) {
System.out.print(i);
st = (int) Math.sqrt(i);

for (j = 2; j <= st + 1; j++) {
if (i % j == 0 && i != 2) {
b = i / j;
hs.add(j);
hs.add(b);
countDivs++;

if (countDivs == 1)
System.out.print(": złożona. Dzielniki: ");
}

if (j == st + 1 && countDivs >= 1) {
List sortedList = new ArrayList(hs);
Collections.sort(sortedList);
System.out.print(sortedList);
}

if (j == st + 1 && countDivs == 0) {
System.out.print(": PIERWSZA ");
countPrime++;

if (i == 2)
distance = 0;
else
distance = i - k;
System.out.print(" Odstęp: " + (distance));
k = i;
}
}
countDivs = 0;
hs.clear();
System.out.println();
}
t1 = System.currentTimeMillis();
t = t1 - t0;
System.out.println("\nZnalezionych liczb pierwszych: " + countPrime + ", w czasie: " + t + " ms" + " (" + t * 0.001 + " s).");
}
}

Zostaw odpowiedź

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