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. static 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. static bool czyPierwsza(int a) {
2.   for (int i = 2; i <= Math.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. static bool czyPierwsza(int a) {
2.   if (a % 2 == 0)
3.     return (a == 2);
4.   for (int i = 3; i <= Math.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.

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. static void Main(string[] args) {
2.   int a;
3.   Console.WriteLine("Wpisz liczbę do sprawdzenia czy jest liczbą Pierwszą");
4.   a = Convert.ToInt32(Console.ReadLine());
5.   Console.WriteLine("Liczba {0} {1}jest pierwsza", a, (czyPierwsza(a) ? "" : "nie "));
6.   Console.ReadKey();
7. }

• 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