Strona główna » Algorytmy » Teoria Liczb » Liczby Nigdy Pierwsze
 

Liczby Nigdy Pierwsze

https://mattomatti.com/a0159
· część 1 ·

Definicja

Liczby Nigdy Pierwsze to takie liczby naturalne, które po zmianie jednej cyfry na dowolną nie mają szans przekształcić się w liczbę pierwszą. Istnieje nieskończenie wiele takich liczb.

Przykład

Najmniejszą liczbą Nigdy Pierwszą jest 200, ponieważ nie można tak zmienić jednej cyfry, aby otrzymać liczbę pierwszą. Jednak 202 już jest, ponieważ można zmienić pierwszą cyfrę 2 na 0 i wtedy otrzymujemy 002 = 2, a 2 to z kolei najmniejsza liczba pierwsza. Warto zauważyć, że każda liczba mniejsza od 10 jest pierwsza ze względu np. na liczbę 2.

Ciąg liczb

Liczby Nigdy Pierwsze można ustawić w następujący ciąg liczb: 200, 204, 206, 208, 320, 322, 324, 325, 326, 328, ...

Implementacja

Założenie

Najprostszy algorytm, który może posłużyć do wyszukiwania liczb Nigdy Pierwszych będzie polegał za zamianie każdej na każdą inną możliwą. Do podmieniania konkretnej cyfry zostanie napisana specjalna funkcja oraz zostanie wykorzystana funkcja do sprawdzenie czy po podmiance liczba jest Pierwsza czy nie. Sprawdzenie czy pojedyncza liczba jest ma złożoność O(10k), gdzie k to ilość cyfr w zapisie liczby. Oznacza to, że złożoność bardzo szybko rośnie dla kolejnych liczb.

Czy liczba Pierwsza

Poniższa funkcja do sprawdzenia czy przekazana liczba jest Pierwsza została szerzej wyjaśniona w tym artykule. W wyniku zwracana jest wartość logiczna.

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

Podmiana cyfry

Poniższa funkcja zamienCyfre() przyjmuje następujące argumenty: a - liczbę w której cyfra ma zostać podmieniona, poz - która kolejna cyfra ma zostać podmieniona (cyfra 0 to cyfra najmniej znacząca) oraz c - nowa cyfra.

  1. int zamienCyfre(int a, int poz, int c) {
  2.   int koniec = pow(10, poz);
  3.   int prawa = a % koniec;
  4.   int lewa = a / (koniec * 10);
  5.   return (lewa * 10 + c) * koniec + prawa;
  6. }

Algorytm dzieli liczbę na dwie częście: na lewo od zamienianej cyfry oraz na prawo. Następnie zwracany jest wynik, który jest połączeniem obu części i wstawionej pomiędzy nimi cyfry c.

Funkcja główna

Funkcja czyNigdyPierwsza() sprawdza dla przekazanej liczby a czy jest ona żądanego typu. Jako wynik zwracana jest wartość logiczna.

  1. bool czyNigdyPierwsza(int a) {
  2.   int dl = log10(a) + 1;
  3.   for (int i = 0; i < dl; i++) {
  4.     for (int c = 0; c <= 9; c++) {
  5.       int b = zamienCyfre(a, i, c);
  6.       if (czyPierwsza(b)) {
  7.         return false;
  8.       }
  9.     }
  10.   }
  11.   return true;
  12. }

Dla każdej cyfry liczby a jest wyliczana liczba z podmienioną cyfrą. Jeśli wyliczona liczba jest pierwsza to zwracany jest fałsz co oznacza, że liczba ma szansę być pierwsza po podmiance jednej cyfry. Jeśli jednak w pętli nie zostanie znalezione rozwiązanie to algorytm zwraca wartość prawda, ponieważ taka liczba nie może zostać w jednej zamianie stać się liczbą pierwszą.

Testowanie funkcji

W celu przetestowania napisanych funkcji można skorzystać z poniższego kodu, który wczyta liczbę, a następnie wypisze o niej informację.

  1. int main() {
  2.   int a;
  3.   cout << "Podaj liczbe do sprawdzenia\n a = ";
  4.   cin >> a;
  5.   bool wynik = czyNigdyPierwsza(a);
  6.   cout << (wynik ? "nie " : "") << "moze byc pierwsza!";
  7.   system("pause");
  8.   return 0;
  9. }