Способов подсчета безграничных простых чисел

Хорошо, так что, возможно, мне не следовало слишком сильно сокращать этот вопрос... Я видел сообщение о наиболее эффективном способе найти первые 10000 простых чисел. Я ищу все возможные пути. Цель состоит в том, чтобы иметь единый магазин для тестов на первичность. Любые тесты, которые люди знают для поиска простых чисел, приветствуются.

Так что:

  • Каковы все различные способы нахождения простых чисел?
Источник

8 ответов

Некоторые простые тесты работают только с определенными числами, например, тест Лукаса-Лемера работает только для чисел Мерсенна.

Большинство простых тестов, используемых для больших чисел, могут только сказать вам, что определенное число "вероятно простое" (или, если число не проходит тест, оно определенно не простое). Обычно вы можете продолжать алгоритм, пока у вас не будет очень высокой вероятности того, что число будет простым.

Взгляните на эту страницу и особенно на раздел "Смотрите также".

Я думаю, что тест Миллера-Рабина является одним из лучших. В своей стандартной форме он дает вам вероятные простые числа - хотя было показано, что если вы примените тест к числу ниже 3,4*10^14, и он пройдет тест для каждого параметра 2, 3, 5, 7, 11, 13 и 17, это определенно премьер.

Тест AKS был первым детерминированным, проверенным, общим тестом за полиномиальное время. Тем не менее, насколько мне известно, его лучшая реализация оказывается медленнее, чем другие тесты, если ввод не является смехотворно большим.

Источник

Вопрос @akdom ко мне:

Цикл работал бы хорошо на моем предыдущем предложении, и вам не нужно делать какие-либо вычисления, чтобы определить, является ли число четным; в вашем цикле просто пропустите каждое четное число, как показано ниже:

//Assuming theInteger is the number to be tested for primality.
// Check if theInteger is divisible by 2.  If not, run this loop.
//  This loop skips all even numbers.
for( int i = 3; i < sqrt(theInteger); i + 2) 
{
    if( theInteger % i == 0) 
    {
       //getting here denotes that theInteger is not prime 
       // somehow indicate that some number, i, divides it and break
       break;
    }
}
Источник

Сито Эратосфена - достойный алгоритм:

  1. Возьмите список положительных целых чисел 2 для любого заданного потолка.
  2. Возьмите следующий элемент в списке (2 в первой итерации) и удалите все его кратные (кроме первого) из списка.
  3. Повторите шаг два, пока не достигнете указанного потолка.
  4. Ваш список теперь состоит исключительно из простых чисел.

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

Источник

Для данного целого числа самая быстрая проверка простоты, которую я знаю:

  1. Возьмите список от 2 до квадратного корня из целого числа.
  2. Перебрать список, беря остаток от целого / текущего числа
    1. Если остаток равен нулю для любого числа в списке, то целое число не простое.
    2. Если остаток был ненулевым для всех чисел в списке, то целое число является простым.

Он использует значительно меньше памяти, чем Сито Эратосфена и, как правило, быстрее для отдельных чисел.

Источник

Аспирант Rutgers недавно нашел рекуррентное отношение, которое генерирует простые числа. Разница его последовательных чисел будет генерировать либо простые числа, либо 1.

a(1) = 7
a(n) = a(n-1) + gcd(n,a(n-1)).

Это делает много дерьма, которое должно быть отфильтровано. Benoit Cloitre также имеет такой рецидив, который выполняет аналогичную задачу:

b(1) = 1
b(n) = b(n-1) + lcm(n,b(n-1))

тогда отношение последовательных чисел, минус один [b(n)/b(n-1)-1] является простым. Полный отчет обо всем этом можно прочитать на рекурсивном.

Что касается сита, вы можете добиться большего успеха, используя колесо вместо того, чтобы добавлять его каждый раз, посмотрите Улучшенные сита с простыми простыми числами. Вот пример колеса. Давайте посмотрим на цифры, 2 и 5, чтобы игнорировать. Их колесо есть, [2,4,2,2].

Источник

В вашем алгоритме, использующем список от 2 до корня целого числа, вы можете улучшить производительность, проверяя только нечетные числа после 2. То есть, ваш список должен содержать только 2 и все нечетные числа от 3 до квадратного корня из целого числа, Это сокращает количество повторений цикла без увеличения сложности.

Источник

@theprise

Если бы я хотел использовать инкрементный цикл вместо экземпляра списка (проблемы с памятью для больших чисел...), что было бы хорошим способом сделать это без построения списка?

Не похоже, что было бы дешевле сделать проверку делимости для данного целого числа (X % 3), чем просто проверку для нормального числа (N % X).

Источник

Если вы хотите найти способ генерации простых чисел, это было рассмотрено в предыдущем вопросе.

Источник
Другие вопросы по тегам