Strona główna » Algorytmy » Teoria Liczb » Liczby Pomiędzy Pierwszymi
 

Liczby Pomiędzy Pierwszymi

Wstęp

Liczby Pomiędzy Pierwszymi to takie liczby naturalne, które są średnimi dwóch kolejnych nieparzystych liczb pierwszych.

Pierwsze dziesięć wyrazów ciągu tego rodzaju liczb to: 4, 6, 9, 12, 15, 18, 21, 26, 30, 34, ..

Spostrzeżenia

Dowodzi się, że tego rodzaju liczba nie może być liczbą pierwszą, ponieważ oznaczałoby to, że wybrane dwie liczby pierwsze nie były kolejnymi.

Implementacja

Liczby pierwsze

W celu sprawdzenia czy dana liczba jest liczbą pierwszą można skorzystać z dowolnej implementacji takiej funkcji z artykułu o liczbach pierwszych. W tej implementacji zostanie wykorzystana najczęściej spotykana i szybka wersja algorytmu:

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

Liczby Pomiędzy Pierwszymi

W celu znalezienia liczb Pomiędzy Pierwszymi należy znaleźć dwie kolejne liczby pierwsze. Oznaczmy mniejszą liczbę pierwszą przez a, a większą przez b. Wtedy wartość szukana pomiędzy nimi to (a - b)/2. W każdej następnej iteracji należy znaleźć kolejną liczbę pierwszą c i przyjąć, że a = b, a potem b = c, aby otrzymać kolejną parę kolejnych liczb pierwszych do znalezienia kolejnej liczby.

Poniżej został zamieszczony kod, który wypisuje n kolejnych liczb Pomiędzy Pierwszymi:

  1. void szukajLiczbPomiedzyPierwszymi(int n) {
  2.   int a = 2;
  3.   int b = 3;
  4.   while (n-- > 0) {
  5.     a = b;
  6.     do {
  7.       b++;
  8.     } while (!czyPierwsza(b));
  9.     cout << (a + b) / 2 << endl;
  10.   }
  11. }

(2. - 3.) Początkowo przyjmujemy dwie liczby pierwsze za pierwszą parę, ale jest ona niepoprawna, ponieważ a jest parzyste. (4.) W pętli dopóki są liczby do wypisania: (5.) przypisujemy zmiennej a wartość b, a następnie (6. - 8.) szukamy następnej liczby pierwszej i przypisujemy do b. W tym przypadku wynik jest (9.) tylko wypisywany na ekran.

Testowanie funkcji

W tym przypadku przetestowanie funkcji polega jedynie na wywołaniu funkcji. Zadanie to można utrudnić tak, aby funkcja zwrócała listę liczb Pomiędzy Pierwszymi.

  1. int main () {
  2.   szukajLiczbPomiedzyPierwszymi(10);
  3.   system("pause");
  4.   return 0;
  5. }

Zadania

Zadanie 1

Napisz funkcję pomiedzyPierwszymiPrzedział(int p, int q), która sprawdzi ile liczb Pomiędzy Pierwszymi mieści się w przedziale [p, q].