Liczby pierwsze – Magia i Programowanie

Liczby pierwsze – zdecydowanie jedne z bardziej owianych sławą liczb. Ich „magiczną” 🧙 mocą jest umiejętność dzielenia się jedynie przez 1 lub przez siebie. No i co w tym magicznego? – Zapytasz 🤔. Są osoby, które potrafią wymieniać po kolei liczby pierwsze aż do np. kilkuset. Może i Ty to zrobisz, po tym artykule. Co jednak z naprawdę dużymi liczbami – Czy tak łatwo określić, czy dana liczba jest liczbą pierwszą? I tu zaczynają się trudności i trochę też ta magia liczb pierwszych 🙂

W tym materiale chcę Ci powiedzieć – czym są liczby pierwsze i jakie mają zastosowanie. Przedstawię Ci również algorytm, dzięki, któremu sprawdzisz, czy masz do czynienia z liczbą pierwszą.

Java – Liczby pierwsze – wprowadzenie

Z tego materiału dowiesz się:

• Czym są liczby pierwsze?
• Jakie jest zastosowanie liczb pierwszych?
• Jak wygląda algorytm – metoda Brute Force?
• Jak wygląda algorytm – Sito Eratostenesa?

Liczby pierwsze

Liczby pierwsze to rodzaj liczb naturalnych, które mogą być podzielone tylko przez 1 i siebie np. 2, 3, 5, 7, 11 czy 13.

Ciekawostką może być fakt, że 2 jest jedyną parzystą liczbą pierwszą – reszta to liczby nieparzyste.

Liczby pierwsze – Historia

Historia liczb pierwszych sięga czasów starożytnych, a dowody zainteresowania liczbami pierwszymi można znaleźć w pracach starożytnych greckich matematyków, takich jak Euklides czy Eratostenes. Eratostenesowi przypisuje się opracowanie tzw. Sita Eratostenesa, które jest metodą znajdowania wszystkich liczb pierwszych do danej granicy.

Natomiast Euklides w swojej książce „Elementy” kompleksowo analizuje liczby pierwsze, w tym daje również dowód, że istnieje nieskończenie wiele liczb pierwszych.

Przez tysiąclecia liczby pierwsze były badane i stosowane w różnych dziedzinach np. do budowy skal muzycznych i systemów strojenia.

Obecnie liczby pierwsze nadal stanowią aktywny obszar badań w matematyce, z wieloma otwartymi problemami i nierozwiązanymi pytaniami.

Liczby pierwsze – Zastosowanie

Liczby pierwsze przez swoje wyjątkowe właściwości mają kilka ciekawych zastosowań w matematyce oraz informatyce np. są one używane:

• w kryptografii do kodowania i dekodowania wiadomości,
• w różnych algorytmach komputerowych np. do generowania kodów haszujących,
• do generowania liczb losowych.

Liczby pierwsze – Algorytm – Metoda Brute Force

Istnieją różne algorytmy sprawdzające liczby pierwsze. Jednym z takich algorytmów jest tzw. Metoda Brute Force. Jest to prosty algorytm, który polega na sprawdzeniu, czy podana liczba jest podzielna przez liczby z zakresu od 2 do pierwiastka kwadratowego podanej liczby. Jeśli nasza liczba jest podzielna przez dowolną liczbę całkowitą z tego zakresu, to znaczy, że nie jest ona liczbą pierwszą – jeżeli nie zostanie znaleziony, żaden dzielnik w tym zakresie, to podana przez nas liczba jest liczbą pierwszą :).

Algorytm ten jest jednak bardzo wolny 🐢 dla dużych liczb. Alternatywą z dużą lepszą wydajnością jeżeli chodzi o duże liczby, jest już bardziej skomplikowany algorytm – Test pierwotności Millera-Rabina.

Liczby pierwsze – Metoda Brute Force – Java

Przyjrzyjmy się bliżej algorytmowi sprawdzającemu, czy dana liczba jest liczbą pierwszą.

    public static boolean isPrime(int n) {
        if (n <= 1) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

W powyższym kodzie sprawdzamy, czy podana liczba n spełnia warunki, aby być liczbą pierwszą – może posiadać jedynie dwa dzielniki: 1 i swoją wartość.

• Najniższą liczbą pierwszą jest 2, dlatego z góry wiadomo, że wszystkie liczby mniejsze od niej nie są liczbami pierwszymi
• W następnym kroku w pętli sprawdzamy, czy podana liczba jest podzielna przez inny dzielnik, jeżeli tak to nasza liczba nie jest liczbą pierwszą.
• Zwróć uwagę, że warunkiem końcowym pętli jest pierwiastek kwadratowy podanej liczby – W metodzie Brute Force pętla może iterować się tak długo aż warunek początkowy pętli będzie mniejszy od naszej liczby – Algorytm jest jednak wtedy mniej wydajny.
• Jeżeli przejdziemy przez całą iterację pętli, oznacza to, że nasza liczba jest liczbą pierwszą 🙂 🏆

Kurs Java – Darmowy Kurs Programowania w Javie

W ramach tego materiału skupiliśmy się na liczbach pierwszych. Jeżeli chcesz kontynuować swoją przygodę z Javą i poznać różne struktury, które oferuję ten język programowania – to zapraszam do zapoznania się z różnymi tematami z serii o Javie.
➡ ZOBACZ 👉: Kurs Java | Darmowy Kurs Programowania w Javie

Liczby pierwsze – Algorytm – Sito Eratostenesa (ang. Sieve of Eratosthenes)

Przedstawiłam Ci już algorytm, który sprawdza, czy podana liczba jest liczbą pierwszą. Możliwe jednak, że zajdzie potrzeba znalezienia wszystkich liczb do jakiejś wartości – sprawdzanie po kolei każdej wartości wydaje się, lekko mówiąc syzyfową pracą.

Istnieje gotowy algorytm stworzony przez Eratostenesa tzw. Sito Eratostenesa, które sprawdza wszystkie liczby z danego zakresu.

Algorytm ten polega na utworzeniu tablicy boolean o rozmiarze n + 1, gdzie n jest liczbą, która jest podanym przez nas punktem końcowym sprawdzanego zakresu. Algorytm iterując się, przez tablicę, oznacza wszystkie liczby, które nie są liczbami pierwszymi. Na końcu procesu wszystkie nieoznaczone liczby są naszym wynikiem – liczbami pierwszymi.

Liczby pierwsze – Sito Eratostenesa – Java

    public static void sieveOfEratosthenes(int n) {
        boolean[] isPrime = new boolean[n+1];
        Arrays.fill(isPrime, true);

        for (int i = 2; i*i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i*i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                System.out.print(i + " ");
            }
        }
    }

Spójrzmy, co wydarzyło się w powyższym kodzie:

• Utworzyłam tablicę booleans isPrime z n+1 elementami, reprezentującymi liczby od 0 do n.
• Wszystkie elementy tablicy zainicjalizowałam z wartością true, ponieważ wszystkie liczby są początkowo uważane za potencjalne liczby pierwsze.
• Tworzę jedną pętlę, w której iteruje się po wszystkich liczbach od 2 tak długo aż nasze n jest mniejsze niż warunek początkowy i do potęgi 2.
• W pierwszej pętli tworzę drugą zagnieżdżoną pętlę, w której oznaczone zostają wszystkie wielokrotności zmiennej „i” jako liczby, które nie są pierwszymi – W naszej tablicy isPrime pozycje, będące odpowiednikami naszych sprawdzanych liczb, oznaczone zostają jako false.
• W ostatnim kroku iterujemy się przez wszystkie elementy od pozycji 2 naszej tablicy i wyświetlamy liczby, oznaczone jako pierwsze.

Zwróć też uwagę, że algorytm przyjmuje jako parametr int, więc ma ograniczenie wielkości sprawdzanego zakresu, aby kod działał przy większych zakresach, konieczne byłoby odpowiednie zmienienie typów na long również wewnątrz algorytmu.

Jest to bardziej skomplikowany algorytm niże metoda Brute Force, dlatego polecam przedebugować się przez ten kod krok po kroku, aby lepiej zrozumieć jego działanie :).

Java – Debugowanie

W ramach tego materiału zajmiemy się przede wszystkim liczbami pierwszymi – natomiast kompletny materiał dotyczący debugowania znajdziesz poniżej.

➡ ZOBACZ 👉: Debugowanie, jakiego jeszcze nie znałeśmienne i typy danych

Java – Liczby pierwsze – Podsumowanie

W ramach tego materiału dowiedzieliśmy się, czym są liczby pierwsze – liczby, które mają tylko dwa dzielniki: 1 oraz siebie samą. Wiemy, że znajdują swoje zastosowanie m.in. w kryptografii oraz w różnych algorytmach komputerowych.

Poznaliśmy, dwa różne algorytmy do sprawdzania liczb pierwszych: prostszy – metodę Brute Force oraz bardziej złożone Sito Eratostenesa. Rozumiemy już jak je zaimplementować i jak działają.