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

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

1. Take the list of positive integers 2 to any given Ceiling.
2. Take the next item in the list (2 in the first iteration) and remove all multiples of it (beyond the first) from the list.
3. Repeat step two until you reach the given Ceiling.
4. Your list is now composed purely of primes.

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

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

1. Take a list of 2 to the square root of the integer.
2. Loop through the list, taking the remainder of the integer / current number

   1. If the remainder is zero for any number in the list, then the integer is not prime.
   2. If the remainder was non-zero for all numbers in the list, then the integer is prime.

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

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

@theprise

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

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

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

Вопрос @ 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;
    }
}

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

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

Из него получается много мусора, который нужно отфильтровать. Бенуа Клойтр также имеет это повторение, которое выполняет аналогичную задачу:

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].

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

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

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

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

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