Wyznaczanie liczb pierwszych - teoria

Algorytm wyznaczania liczb pierwszych przez sprawdzanie dzielników

Algorytm wyznaczania liczb pierwszych poprzez sprawdzanie dzielników polega na sprawdzaniu, czy dana liczba ma dzielniki inne niż 1 i sama siebie. Jeśli takie dzielniki istnieją, liczba jest liczbą złożoną i nie jest liczbą pierwszą. Jeśli nie ma innych dzielników, liczba jest uznawana za liczbę pierwszą.

Kluczowa idea

Algorytm opiera się na prostym fakcie, że liczba n jest liczbą pierwszą, jeśli ma dokładnie dwa dzielniki: 1 i samą siebie. Aby sprawdzić, czy liczba n jest liczbą pierwszą, należy przetestować wszystkie potencjalne dzielniki z przedziału od 2 do √n. Jeśli liczba n nie ma dzielnika w tym przedziale, uznajemy ją za liczbę pierwszą.

Iteracyjny opis algorytmu

1. Zdefiniuj liczbę n, którą chcesz sprawdzić.

2. Jeśli n jest mniejsze niż 2, nie jest liczbą pierwszą.

3. Dla każdej liczby d z przedziału od 2 do √n :

   • Jeśli n dzieli się przez d, liczba n nie jest liczbą pierwszą.

4. Jeśli po przetestowaniu wszystkich dzielników liczba nie dzieliła się przez żaden z nich, to n jest liczbą pierwszą.

5. Zakończ algorytm, zwracając wynik.

Przykład działania

Rozważmy liczbę 29 i sprawdźmy, czy jest liczbą pierwszą:

• Krok 1: 29 jest większe od 2, więc można kontynuować.

• Krok 2: Sprawdzamy, czy 29 dzieli się przez liczby z przedziału [2,√29], czyli 2,3,4,5.

• Krok 3: 29 nie dzieli się przez żadną z tych liczb, więc 29 jest liczbą pierwszą.

Złożoność algorytmu

Złożoność czasowa algorytmu wynosi O(√n ), ponieważ liczby pierwsze są sprawdzane na podstawie dzielników tylko do √n. To znacząco przyspiesza algorytm w porównaniu do pełnego testowania wszystkich liczb od 2 do n−1.

Zastosowanie algorytmu

Algorytm ten jest przydatny do prostego i efektywnego sprawdzania, czy dana liczba jest pierwsza. Znajduje zastosowanie w różnych dziedzinach, takich jak analiza liczb, algorytmy numeryczne czy kryptografia.

Wykaz początkowych liczb pierwszych:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97...

Pseudokod - wyznaczania liczb pierwszych

Algorytm wyznaczania liczb pierwszych polega na sprawdzaniu, czy dana liczba nie ma dzielników innych niż 1 i sama siebie. W każdym kroku, jeśli zostanie znaleziony dzielnik, liczba jest pomijana. W przeciwnym razie, jeśli nie ma dzielników, liczba jest uznawana za pierwszą i wyświetlana.

Algorytm wyznaczania liczb pierwszych

Wejście:

• n - liczba, którą chcemy sprawdzić pod kątem pierwszości.

Wyjście:

• n - jeżeli n jest liczbą pierwszą, to ją wyświetlamy.

Zmienne pomocnicze:

• d - zmienna przechowująca potencjalne dzielniki (od 2 do sqrt(n)). cmath - biblioteka potrzebna do funkcji sqrt()

Lista kroków:

K1:   Jeśli n < 2  
      to zwróć (n nie jest liczbą pierwszą)
K2:   Dla d od 2 do sqrt(n)  
      wykonuj kroki od K3 do K4
K3:   Jeśli n % d = 0  
      to zwróć (n nie jest liczbą pierwszą)
K4:   Zakończ pętlę
K5:   Wyświetl n   (n jest liczbą pierwszą)

Wynik działania programu:

Podaj liczbe: 29
29 jest liczba pierwsza.