Liczby Pierwsze

Rozmieszczenie liczb pierwszych w zakresie od 1 do 60 włącznie

Definicja

Liczba pierwsza to taka liczba, która ma dokładnie dwa dzielniki: 1 oraz samą siebie. Najmniejszą liczbą pierwszą jest 2.

Przykład

Kilka pierwszych liczb pierwszych to: 2, 3, 5, 7, 11, 13, 17, 19, 23, ..

Implementacja

Rozwiązanie proste

Pierwszym pomysłem na rozwiązanie jakie się nasuwa jest sprawdzenie wszystkich liczb mniejszych od podanej, aby sprawdzić czy liczba jest pierwsza. Wtedy kod wyglądałby prawdopodobnie tak:

1. bool czyPierwsza(int a) {
2.   for (int i = 2; i < a; i++) {
3.     if (a % i == 0) {
4.       return false;
5.     }
6.   }
7.   return true;
8. }

(1.) Funkcja czyPierwsza() przyjmuje jeden argument a. (2.) Dla każdej liczby z zakresu [2, a) (3.) sprawdź czy nie dzieli a. Jeśli którakolwiek i-ta liczba dzieli a to (4.) zwróć fałsz. Jeśli jednak pętla for nie zostanie, ani razu przerwana to zwróć prawdę, ponieważ liczba jest pierwsza.

Rozwiązanie optymalne

Rozwiązanie proste ma złożoność liniową , ponieważ dla dowolnej liczby a zostanie wykonane a - 1 sprawdzeń. Zakres poszukiwania dzielników liczby można ograniczyć z góry przez , ponieważ jest to ostatnia liczba, która może być dzielnikiem liczby a. W poprzednim kodzie należy poprawić zaledwie jedna linijkę, aby uzyskać złożoność algorytmu

1. bool czyPierwsza(int a) {
2.   for (int i = 2; i <= sqrt(a); i++) {
3.     if (a % i == 0) {
4.       return false;
5.     }
6.   }
7.   return true;
8. }

Warto jednak zwrócić uwagę na to, że pierwiastek liczby a też może być dzielnikiem liczby a, dlatego tym razem przedział z prawej strony musi być domknięty.

Dalsza optymalizacja

Po dokładnym przyjrzeniu się liczbom pierwszym nietrudno zauważyć, że jedyną parzystą liczbą pierwszą jest 2. Ta informacja pozwoli na dalszą optymalizację kodu. Z ograniczonego zakresu sprawdzone zostaną jedynie nieparzyste wartości. Należy jednak pamiętać, aby sprawdzić czy podana liczba a nie jest parzysta.

1. bool czyPierwsza(int a) {
2.   if(a % 2 == 0)
3.     return (a == 2);
4.   for (int i = 3; i <= sqrt(a); i += 2) {
5.     if (a % i == 0) {
6.       return false;
7.     }
8.   }
9.   return true;
10. }

(2.) W tym przypadku na początku należy sprawdzić czy liczba jest parzysta. W przypadku, gdy jest to (3.) wynikiem będzie sprawdzenia czy a to 2. Program zwróci wtedy prawidłowo, że 2 jest pierwsza, ale żadna inna parzysta liczba już nie. (4. - 9.) Dalsze poszukiwania dzielnika odbywają się w sposób identyczny jak w dwóch poprzednich przypadkach. Różnica jednak polega na (4.) rozpoczęciu szukania dzielnika od 3 i zwiększaniu wartości i o 2 po każdej iteracji.

Zastosowanie tej metody wyszukiwania dzielników pozwoliło wykonywać dwa razy mniej operacji dzielenia podczas szukania dzielników. Jest to najlepsze rozwiązanie ze wszystkich wymienionych.

Testowanie kodu

Do przetestowania dowolnego powyższego kodu można użyć poniższej funkcji main(). Po uruchomieniu program zapyta się o liczbę, którą ma sprawdzić czy jest pierwsza.

1. int main () {
2.   int a;
3.   cout << "Wpisz liczbe do sprawdzenia czy jest liczba pierwsza:\n";
4.   cin >> a;
5.   cout << "Liczba " << a << (czyPierwsza(a) ? "" : " nie") << " jest pierwsza\n";
6.   system("pause");
7.   return 0;
8. }

• Kod źródłowy Rozwiązanie proste
• Kod źródłowy Rozwiązanie optymalne
• Kod źródłowy Dalsza optymalizacja

Zadania

Zadanie 1

Napisz rekurencyjną wersję sprawdzania czy podana liczba jest pierwsza. W celu sprawdzenia użytkownik powinien podawać jedynie jeden argument a - liczbę do sprawdzania.

• Kod źródłowy Zadanie 1