Как найти n+1 ое простое число за минимальное время?

Question

[Forever_Angel]

Существует ли(и если да, то какой) алгоритм, который получая на вход список из n простых чисел от p_0 = 2 до p_n-1, выдавал бы за не слишком большое время p_n ? Иными словами, есть ли алгоритм, чтобы искать следующее простое число?

Answer 1

[Wataru]

Есть - перебирайте следующее число, начиная с p_(n-1)+1, потом проверяйте делимость на все простые числа, пока они меньше корня и текущего числа.

Можно применить следующие оптимизации - начинать с p_(n+1)+2 и идти с шагом 2 (только нечетные числа). Перебирать числа только вида 6k-1 и 6k+1 (k изначально floor(p_(n-1)+3) / 6). Вместо высчитывания корня, в коде должно быть возведение в квадрат - что-то вроде while (i < n && p[i]*p[i] <= x) ... i++;.

Это если вам уже дан список предыдущих простых чисел. Если же вы думаете над шагом алгоритма, который находит первые n простых чисел или все простые до какого-то K, то быстрее будет использовать решето эратосфена.