Следующее простое число алгоритм

я хочу знать, если есть простой способ найти простое число рядом с X.Следующее простое число алгоритм

Например, если X = 2, то следующий премьер будет 3. Алгоритм, который я есть было бы хорошо, если бы я хотел знать небольшие числа, но я хочу рассчитать, как X = 3 миллиона.

Я нашел алгоритм вычисления простых чисел, но для их вычисления требуется много времени, так как он вычисляет все простые числа от 0 до X ... Например, за 1 миллион требуется около 2 минут.

Вопрос ... Как я могу найти следующее простое число? Есть ли эффективный алгоритм? Лучшее решение, которое я нашел, это проверить, является ли X + 1 простым и увеличиваться до тех пор, пока не будет найдено ...

источник

2015-03-11 Pedro Lino

Поскольку 2 является единственным четным простым числом, вы можете использовать X + 2 (если сам X не 2). Также см. [Здесь] (http://stackoverflow.com/questions/4475996/given-prime-number-n-compute-the-next-prime) – sb9

См. [Это] (http://en.wikipedia.org/ wiki/Sieve_of_Eratosthenes) –

Это занимает много времени @RobbieDee. Это был тот, о котором я говорил. Чтобы сделать больше работы, чем N, я лучше выполняю работу N/2, тогда ... –

Возможное решение вместо увеличения номера на one, вы можете увеличить его число на two, если число нечетное else увеличивается на единицу, а затем во всех будущих итерациях увеличивается на два.

Как в приведенном ниже фрагменте кода

if (num is odd) 
    check_prime_of(num+2); 
else /*num is even and not equal to 2*/ 
    check_prime_of(num+1);

источник

2015-03-11 12:57:51

Отличная идея. Спасибо –

Вы можете дополнительно уменьшить нагрузку, наблюдая, что после 2 и 3 все простые числа имеют вид 6 * N +/- 1, где N - целое число. Вы также можете уменьшить рабочую нагрузку, сохранив таблицу известных простых чисел до некоторого предела, и чем больше таблица, тем меньше стоимость вычислений. –

Это не уменьшает вдвое сложность. O (n) = O (n/2). – mafso

Я могу удвоить скорость в «если х + 1 простое» ..... Для всех х> 2, то х + 1 никогда не будет премьер , поэтому вместо этого тест x + 2)

Кроме этого, нет. Не существует эффективного алгоритма для поиска следующего числа после X. «Долгое время для расчета» - это то, что делает криптографию с открытым ключом (основой большей части безопасности в Интернете). Открытый ключ основан на трудности нахождения двух простых факторов заданного большого числа; если бы найти следующий штрих после X, было бы легко, тогда вы могли бы просто начать с квадратного корня большого числа и начать подсчет.

источник

2015-03-11 12:59:54 racraman

Это было бы, если бы х не было даже правильно? –

Да, не найдется много простых чисел, увеличивающих на 2, если бы х было! :). Я думал об алгоритме, который только что нашел простой «х». – racraman

Неправильная связь с трудностью факторинга. Если бы у вас был постоянный оракул времени, который дал вам следующий премьер, это не дало бы вам коэффициент числа намного быстрее. Пробное деление на простые числа происходит не намного быстрее, чем пробное деление, что довольно далеко от лучших алгоритмов факторинга. –

Что вам нужно, чтобы test for primality каждый номер, начинающийся с X. Вы можете найти такие тесты, реализованные в GMP library, или вы можете посмотреть фрагмент алгоритма Миллера-Рабина в Rosetta code.

источник

2015-03-11 13:00:03 logc

Это полезно. Это не помогает избежать проверки четных чисел, так как проверка на малые простые факторы обычно является первым шагом, поэтому вряд ли потребуется время, чтобы распознать и отклонить числа, делящиеся на 2 или 19. Если X достаточно велико (скажем, тысячи или миллионы цифр), вы можете сделать немного лучше, разделив кандидатов, делящихся на небольшие или умеренные простые числа. –

Следующее простое число алгоритм

ответ

Смежные вопросы