Liczby Super Pierwsze

Definicja

Liczby Super Pierwsze to takie liczby pierwsze, których pozycja na liście liczb pierwszych też jest liczbą pierwszą. Do optymalnego rozwiązania warto wykorzystać sito Eratostenesa. Przykładowo najmniejszą liczbą Super Pierwszą jest 3, ponieważ 3 jest drugą liczbą pierwszą, a 2 też jest liczbą pierwszą.

Ciąg

Liczby Super Pierwsze można ustawić w następujący ciąg: 3, 5, 11, 17, 31, 41, 59, 67, 83, ..

Implementacja

Do generowania liczb Pierwszych zostanie wykorzystane Sito Eratostenesa. W tym celu deklarujemy funkcją Sito, która odpowie czy aktualnie sprawdzana liczba pierwsza jest wśród liczb zmiennej lista.

1. bool Sito(vector<int> &lista, int pierwsza) {
2.   for (int i = 0; i < lista.size(); i++) {
3.     if (pierwsza % lista[i] == 0) {
4.       return false;
5.     }
6.   }
7.   return true;
8. }

Powyższa funkcja pomoże sprawdzić czy dana liczba jest Super Pierwsza. Początkowo sprawdzamy czy liczba jest mniejsza od 2. Jeśli tak to na pewno nie jest to liczba Super Pierwsza. Następnie wyznaczamy wszystkie liczby w zakresie [2, a].

1. bool CzySuperPierwsza(int a) {
2.   if (a < 2) {
3.     return false;
4.   }
5.   vector<int> lista;
6.   int pierwsza = 2;
7.   while (pierwsza <= a) {
8.     if (Sito(lista, pierwsza)) {
9.       lista.push_back(pierwsza);
10.     }
11.     pierwsza++;
12.   }
13.   int pozycja = lista.size();
14.   if (lista[pozycja - 1] == a) {
15.     for (int i = 0; i < lista.size(); i++) {
16.       if (lista[i] == pozycja) {
17.         return true;
18.       }
19.     }
20.   }
21.   return false;
22. }

Po wyznaczeniu liczb Pierwszych należy sprawdzić czy ostatnia wartosć do aktualnie sprawdzana liczba. Jeśli tak to teraz wystarczy sprawdzić czy jej pozycja na liście jest liczbą pierwszą. Przy wyznaczaniu pozycji należy pamiętać, że indeksujemy od 1.

Testowanie funkcji

Do sprawdzenia czy powyższa funkcja działa można uruchomić poniższy fragment programu:

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

• Kod źródłowy Implementacja