@Forever_Angel

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

Существует ли(и если да, то какой) алгоритм, который получая на вход список из n простых чисел от p_0 = 2 до p_n-1, выдавал бы за не слишком большое время p_n ? Иными словами, есть ли алгоритм, чтобы искать следующее простое число?
  • Вопрос задан
  • 101 просмотр
Пригласить эксперта
Ответы на вопрос 1
wataru
@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, то быстрее будет использовать решето эратосфена.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы