Liczby pierwsze

Spis treści Poprzednia strona: Ciąg Fibonacciego Następna strona: Pliki i struktury

Zwykle pamiętamy ze szkoły, że liczby pierwsze to takie, które dzielą się tylko przez jeden i przez samą siebie, i że są to takie liczby, jak: 2, 3, 5, 7, 11, 13, … Oto kilka dodatkowych faktów:

  • wszystkie oprócz dwójki są nieparzyste
  • liczb pierwszych jest nieskończenie wiele
  • dla dużej liczby ogólnie ciężko jest stwierdzić czy jest ona liczbą pierwszą, czy nie
  • kolejne liczby pierwsze mogą różnić się między sobą o 2 (liczby bliźniacze), albo mogą być dowolnie daleko od siebie
  • gdy znamy jakąś liczbę pierwszą, nie ma reguły na znalezienie kolejnej liczby pierwszej

A gdybyśmy tak chcieli znaleźć tysiąc liczb pierwszych, albo milion? Nie ma żadnego problemu. Musimy jednak mieć algorytm, który to za nas zrobi. Wróćmy jeszcze raz do definicji liczb pierwszych: „dzielą się tylko przez jeden i przez samą siebie”. Zaraz, zaraz. Każda liczba dzieli się przez 1  (bo N / 1 = N) i przez samą siebie (bo N / N = 1). Co w tym dziwnego? „Dzielą się tylko przez jeden i przez samą siebie” – słowo „tylko” łatwo przeoczyć, a ono jest tutaj najważniejsze. Oznacza, że liczba pierwsza p nie dzieli się przez żadną z liczb 2, 3, 4, …, p-3, p-2, p-1. Wystarczy „przejechać” pętlą po tych liczbach i sprawdzić, czy dana liczba dzieli się przez nie wszystkie, czy nie. Wystarczy, że znajdziemy jedną taką liczbę d, że n / d daje resztę równą zero (tj. liczba n dzieli się przez d bez reszty, albo liczba d jest dzielnikiem liczby n) i będzie to oznaczało że liczba n nie jest pierwsza. Jak liczba nie jest pierwsza, to znaczy, że jest złożona. Złożona z czego? Z liczb pierwszych właśnie. Każda liczba złożona jest iloczynem liczb pierwszych. Liczba pierwsza to taka, której nie da się rozłożyć na iloczyn innych liczb – właśnie dlatego, że nie ma ona dzielników. Załóżmy, że mamy N gwiazdek i chcemy je rozłożyć w wierszach i kolumnach jakiejś tablicy tak, żeby wszystkie wiersze i kolumny były całkowicie wypełnione gwiazdkami. Jeśli N = 12 możemy gwiazdki rozłożyć w 3 rzędach po 4, albo w 4 rzędach po 3, albo w 2 rzędach po 6, albo w 6 rzędach po 2, albo w jednym rzędzie po 12, albo w jednej kolumnie po 12. Kiedy N jest liczbą pierwszą – nie mamy tak łatwo, i jedyną możliwością jest jeden wiersz złożony z N gwiazdek, albo jedna kolumna złożona z N gwiazdek. Każde inne rozłożenie gwiazdek na wiersze i kolumny spowoduje, że w jakimś wierszu, albo w jakiejś kolumnie będzie brakować gwiazdek. Koniec dygresji.

Pomysł na taki algorytm jest prosty:

  • zaczynamy od 2 i jest to liczba pierwsza (po prostu)
  • tak naprawdę zaczynamy od 3 i sprawdzamy, czy jest podzielna przez 2 (przez 1 jest podzielna, bo każda jest – to trywialne) i widzimy, że nie jest a więc 3 jest liczbą pierwszą
  • liczby 4 nie sprawdzamy, bo jest parzysta, a więc złożona (każda parzysta jest złożona na pewno z dwójki i z czegoś jeszcze…)
  • liczbę 5 dzielimy przez 2 – nie dzieli się, przez 3 – nie dzieli się, więc ok: 5 jest liczbą pierwszą
  • i tak dalej z 7
  • dla liczby 9 stwierdzimy, że dzieli się przez 3 – więc jest złożona
  • itd.
int[] p = new int[1000]; // w tej tablicy zbieramy liczby pierwsze
p[0] = 2; // na dobry początek
for (int n = 3, i = 1; i < 1000; n+=2) // start od 3, dalej co 2
{
    bool pierwsza = true; // zakładamy, że liczba n jest pierwsza
    for (int k = 1; k < i; k++)
    {
        if (n % p[k] == 0)
        {
            pierwsza = false; // nie, n okazała się być złożona
            break; // kolejnych p[k] nie musimy już sprawdzać
        }
    }
    if (pierwsza) p[i++] = n; // pierwsze wpisujemy do tablicy
}

Mamy tutaj pewne ukryte założenie (czytaj: nieobsłużony potencjalny wyjątek). Zakładamy, że operacja n+=2 nie przekroczy zakresu liczb typu int. To znaczy zakładamy, że tysięczna z kolei liczba pierwsza jest nie większa niż int.MaxValue (przy okazji int.MaxValue jest liczbą pierwszą, największą w zakresie typu int).

Czy na pewno musimy sprawdzać podzielność liczby n przez wszystkie liczby pierwsze dotychczas znalezione? Nie, wystarczy sprawdzać te, które są nie większe od pierwiastka z n. Dlaczego? Pierwiastek z n (sqrt(n)) to taka liczba, przy której dzielnik jest równy ilorazowi (N / sqrt(n) = sqrt(n), bo N = sqrt(n) * sqrt(n)). Ponieważ mnożenie jest przemienne sprawdzanie podzielności przez liczby większe od sqrt(n) jest po prostu powtarzaniem tych samych sprawdzeń, tych samych mnożeń, tylko w odwrotnej kolejności, a więc nie jest potrzebne. Na przykład sprawdzając podzielność n = 27 wystarczy sprawdzić 2, 3 i 5, bo sqrt(27) to w przybliżeniu 5,19. Nie musimy sprawdzać podzielności przez inne mniejsze od 27 liczby pierwsze 7,11,13,19, ani przez 23, bo gdyby 27 było podzielne przez jedną z tych liczb, wynik musiałby być równy 2, 3 lub 5, a to już sprawdziliśmy.

Zmodyfikujmy nasz algorytm, tak aby nie sprawdzał niepotrzebnych wyników dzieleń. Trzeba będzie zamienić warunek k < i w 6 linii na k <= m, gdzie m jest indeksem największej liczby pierwszej z dotychczas znalezionych w tablicy p, i jednocześnie nie większej niż pierwiastek z n. Trzeba taki indeks m znaleźć. Ponieważ liczby w tablicy p są posortowane (wstawiamy je w kolejności rosnącej), to można wyszukiwanie pierwiastka z n wykonać przy pomocy algorytmu wyszukiwania binarnego. Ale czy wyszukiwanie binarne na pewno jest konieczne? Zastanówmy się chwilę. Liczba n rośnie, więc pierwiastek z n też rośnie, tylko wolniej. Czyli nasz indeks m nie będzie się szybko zmieniał i będzie tylko rósł. Wystarczy więc szukać następnej wartości dla m począwszy od poprzedniej, mniejszej lub równej wartości m. Zapiszmy to.

int[] p = new int[1000]; // w tej tablicy zbieramy liczby pierwsze
p[0] = 2; // na dobry początek
p[1] = 3; // na jeszcze lepszy początek (konieczne!)
int m = 0;
for (int n = 5, i = 2; i < 1000; n+=2) // start od 5, dalej co 2
{
    bool pierwsza = true; // zakładamy, że liczba n jest pierwsza
    int r = (int)Math.Sqrt(n); // r to pierwiastek z n
    while (p[m+1] <= r) m++;
    for (int k = 1; k <= m; k++)
    {
        if (n % p[k] == 0)
        {
            pierwsza = false; // nie, n okazała się być złożona
            break; // kolejnych p[k] nie musimy już sprawdzać
        }
    }
    if (pierwsza) p[i++] = n; // pierwsze wpisujemy do tablicy
}

Zwróćmy uwagę na to, co się dzieje dla n = 7. Mamy pierwiastek = 2, więc nadal m = 0 i sprawdzalibyśmy podzielność przez p[k=0] = 2, ale tego nie robimy bo skądinąd wiemy, że 7 jest nieparzyste. Dalej mamy n = 9 i teraz pierwiastek = 3 (sprawdź to w debugerze wykonując program krok po kroku albo ustawiając odpowiednią pułapkę z warunkiem!) oraz m = 1, zatem sprawdzana jest podzielność przez 3 i 9%3==0 jest prawdą, stąd n = 9 jest liczbą złożoną, a nie pierwszą.

Ćwiczenie 1

Wywołanie funkcji obliczającej pierwiastek jest dość kosztowne czasowo i obliczeniowo. Zmodyfikuj powyższy algorytm tak, aby wartość r była algorytmowi znana bez jej jawnego obliczania.

Ćwiczenie 2

Zaimplementuj szukanie indeksu m przy pomocy przeszukiwania binarnego w tablicy p w zakresie od 0 do i. Zastosuj operator przesunięcia bitowego zamiast dzielenia przez 2. Sprawdź czy dla dużych liczb n taki algorytm wykonuje się szybciej, czy wolniej niż algorytm z ćwiczenia 1.

Ćwiczenie 3

Znajdź przedostatnią liczbę pierwszą w zakresie typu int (FYI jest to 2147483629, ale niech to wyjdzie z Twojego algorytmu).

Ćwiczenie 4

Ile wystarczy znać początkowych liczb pierwszych aby móc sfaktoryzować każdą liczbę typu int?

Spis treści Poprzednia strona: Ciąg Fibonacciego Następna strona: Pliki i struktury