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, ..
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.
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:
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:
(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.
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.
Napisz funkcję pomiedzyPierwszymiPrzedział(int p, int q), która sprawdzi ile liczb Pomiędzy Pierwszymi mieści się w przedziale [p, q].