Liczby Emirp

Definicja

Liczby Emirp to takie liczby naturalne, które są liczbami pierwszymi oraz ich zapisanie wspak też jest liczbą pierwszą. Obydwie wartości muszą być różnymi liczbami naturalnymi.

Przykład

Najmniejszą liczbę Emirp jest 13, ponieważ jest ona liczbą pierwszą oraz 31 też. Spełniony jest też warunek, że obie wartości są różne. Przykładem liczby pierwszej, który nie jest liczbą Emirp jest 101, ponieważ zapisana wspak dalej jest 101, więc nie spełnia trzeciego warunku.

Ciąg

Liczby Emirp można ustawić w następujący ciąg: 13, 17, 31, 37, 71, 73, 79, 97, 107, 113, ..

Uwaga

Jednym z najprostszych sposobów na odfiltrowanie z liczb naturalnych liczby pierwsze było odrzucenie wszystkich liczb parzystych różnych od 2. W tym przypadku można to zastosować w celu odfiltrowania liczb Emirp. Potencjalnym kandydatem na liczbę Emirp jest liczba, która pierwszą oraz ostatnią cyfrę ma nieparzystą.

Warto również zauważyć, że jeśli liczba a jest liczbą Emirp to jej zapis wspak również. To spostrzeżenie może się przydać np. do szbkiego generowania liczb Emirp z podanego zakresu.

Implementacja

Czy pierwsza?

Podczas wyszukiwania potrzebna będzie funkcja do sprawdzania czy dana liczba jest Liczbą Pierwszą. Funkcja czyPierwsza() przyjmuje jeden argument a i zwraca wartość logiczną czy a to Liczba Pierwsza.

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. }

Liczba Wspak

Kolejna przydatna funkcja dotyczy zapisywania liczby wspak. Funkcja odwroc() realizuje to zadanie poprzez pobieranie kolejnych cyfr z liczby, a następnie dołączanie ich do liczby wynikowej, a oto kod funkcji:

1. int odwroc(int a) {
2.   int b = 0;
3.   while (a > 0) {
4.     b *= 10;
5.     b += a % 10;
6.     a /= 10;
7.   }
8.   return b;
9. }

Funkcja Główna

Teraz napisanie funkcji sprawdzającej czy dana liczba jest typu Emirp mieści się w zaledwie dwóch linijkach. Pierwsza z nich oblicza liczbę wspak, a w drugiej sprawdzamy wszystkie trzy warunki. Na początku sprawdzamy czy a jest różne od b, aby uniknąć

1. bool czyEmirp(int a) {
2.   int b = odwroc(a);
3.   return (a != b && czyPierwsza(a) && czyPierwsza(b));
4. }

(2.) Najpierw obliczamy liczbę wspak, a w drugiej sprawdzamy wszystkie trzy warunki i zwracamy wynik logiczny. Na początku sprawdzamy czy a jest różne od b, aby uniknąć kosztownego sprawdzania czy a i b są pierwsze skoro nie spełnią prostego do sprawdzenia warunku.

Testowanie funkcji

Napisane funkcje można przetestować przy pomocy poniższego fragmentu kodu:

1. int main () {
2.   int k;
3.   cout << "Do ilu szukac liczb Emirp?\n k = ";
4.   cin >> k;
5.   cout << "W [1, " << k << "] znaleziono:" << endl;
6.   for (int i = 1; i <= k; i++)
7.     if (czyEmirp(i))
8.       cout << i << endl;
9.   system("pause");
10.   return 0;
11. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz funkcję wypiszEmirp(), która będzie wyszukiwać liczby z podanego zakresu [1, k] korzystając z faktu, że jeśli sprawdzimy liczbę a to nie musimy powtarzać sprawdzania dla liczby a zapisanej wspak. W ten sposób ograniczymy czas spędzony na wyznaczeniu liczb do wypisania.

• Kod źródłowy Zadanie 1