Liczby Zgubne

Informacje

Definicja

Liczby Zgubne to takie liczby, których populacja jest liczbą pierwszą. Za populację przyjmuje się liczbę cyfr 1 potrzebnych do zapisu liczby w systemie binarnym.

Przykład

Liczbą zgubną jest np. 17 ponieważ 17 = 10001₂. Jak widać w zapisie binarnym występują dokładnie dwie cyfry 1, a 2 jest liczbą parzystą. Innym przykładem jest liczba 79 = 1001111₂. Tym razem w jej zapisie występuje pięć bitów 1, a 5 jest liczbą pierwszą, więc też jest to liczba Zgubna.

Ciąg liczb

Ustawiając liczby Zgubne w ciąg otrzymuje się: 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, ..

Właściwości

Należy pamiętać, że liczba 0, ani 1 nie są liczbami pierwszymi, więc żadna liczba postaci np. 2ⁿ nigdy nie będzie liczbą Zgubną. Jednak po dodaniu jakiejkolwiek potęgi 2^k w wyniku otrzyma się liczbę ze wspomnianego zbioru. Oznacza to, że liczba pierwsza 2 nie jest liczbą zgubną, ale 3 już tak.

Zadanie

Napisz program, który wypisze pierwsze n liczb Zgubnych, gdzie n jest dodatnią liczbą całkowitą wprowadzona od użytkownika. Przetestuj działanie napisanego programu.

Czy zgubna?

Najważniejszą częścią takiego programu jest funkcja czyZgubna(), która dla podanej liczby n zwróci czy liczba bitów tej liczby jest pierwsza.

1. bool czyZgubna(int n) {
2.   int cyfrjeden = 0;
3.   while (n > 0) {
4.     if(n & 1 == 1)
5.       cyfrjeden++;
6.     n >>= 1;
7.   }
8.   return czyPierwsza(cyfrjeden);
9. }

(2.) Wyzeruj licznik, a następnie (3.) dopóki liczba jest większa od 0 to (4.) sprawdź czy najmniej znaczący bit jest 1. Jeśli tak to (5.) zwiększ licznik. Na koniec iteracji należy pamiętać, aby (6.) usunąć sprawdzony już bit. Po zakończeniu iteracji (8.) trzeba sprawdzić czy w liczniku znajduje się liczba pierwsza.

Funkcją pomocniczą jest tutaj funkcja czyPierwsza(), która zwraca wartość logiczną czy dana liczba jest liczbą pierwszą.

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

Więcej na temat poszukiwań liczb Pierwszych można przeczytać w tym artykule.

Testowanie funkcji

W celu sprawdzenia poprawności działania funkcji poniższy fragment kodu wczytuje od użytkownika ile pierwszych liczb Zgubnych ma wypisać, a następnie rozpoczyna ich poszukiwania.

1. int main () {
2.   int n;
3.   cout << "Ile liczb zgubnych wypisac?\n n = ";
4.   cin >> n;
5.   cout << "Oto pierwsze " << n << " liczb zgubnych:" << endl;
6.   int i = 2;
7.   while (n-- > 0) {
8.     while (!czyZgubna(i))
9.       i++;
10.     cout << i++ << " ";
11.   }
12.   system("pause");
13.   return 0;
14. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz funkcję szukajZgubnych(), który przyjmie dwa argumenty n i k. Następnie wypisz pierwsze n liczb zgubnych o k bitach.

Przykładowo dla n = 5 i k = 5 program powinien wypisać:

1. 31 47 55 59 61

Wyjaśnienie

Liczby mają następujące rozwinięcia binarne, które każde ma dokładnie 5 bitów:

• Kod źródłowy Zadanie 1