Odpowiedź:
To jest jeden z tych problemów, które nie da się rozwiązać w rozsądnym czasie jeśli n będzie zbyt duże.
W moim rozwiązaniu masz zmienną limit, która określa maksymalny przedział poszukiwania liczb bliźniaczych. Zwiększenie tego limitu wydłuży czas działania tej funkcji. W pętlach są warunki i > 0 i j >0 gdyby limit był większy od maksymalnej wartości int i zmienna i lub j wyszła poza zakres zmiennej int.
Wyszukiwanie liczb bliźniaczych "na piechotę" poprzez testowanie kolejnych wartości mija się z celem, dlatego zastosowałem sito Eratostenesa (najlepiej, gdyby to była osobna funkcja generująca tablicę liczb pierwszych, która to tablica byłaby przekazana do funkcji bliźniacze, ale treść zadania na to nie pozwala, a nie chciałem z niej robić zmiennej globalnej) do wygenerowania liczb pierwszych w przedziale <0;limit>, dzięki czemu mogę szybciej (w większości przypadków) odpowiedzieć na zadane pytanie.
int blizniacze(int n)
{
int limit = 100000000;
vector<bool>liczbyPierwsze(limit+1,1);
liczbyPierwsze[0] = liczbyPierwsze[1] = 0;
int i,j;
for(i = 2;i <= sqrt(limit) && i > 0;i++)
if(liczbyPierwsze[i])
for(j = i * i;j <= limit && j > 0; j += i)
liczbyPierwsze[j] = 0;
if(n == 1)
return 3;
for(i = 6;i <= limit;i+=6)
if(liczbyPierwsze[i-1] == liczbyPierwsze[i+1] && liczbyPierwsze[i-1])
{
n--;
if(n == 1)
break;
}
if(n == 1)
return i - 1;
else
return -1; //w zadanym limicie nie ma n-tej pary liczb blizniaczych
}
Wyjaśnienie:
