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

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

И так:

  • Каковы все различные способы нахождения простых чисел?
10.08.2008 18:11:08
Обратите внимание, что вы можете сосчитать число простых чисел ниже n, не вычисляя их все: en.wikipedia.org/wiki/…
Jeffrey Bosboom 13.07.2015 01:20:53
8 ОТВЕТОВ

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

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

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

2
10.08.2008 18:30:02
здесь отсутствует ключевая деталь: как вы находите и как «удалить» кратные. Если вы найдете их надлежащим образом, то есть отсчитываете от простого числа по шагам этого простого числа, вы вообще не сможете их удалить , потому что тогда вы не сможете считать . Смысл SoE в том, чтобы пометить мультипликаторы, используя их значения в качестве адресов , без какого-либо сравнения значений (что позволяет избежать дополнительного log nфактора сложности). Это похоже на то, что делает целочисленные сортировки быстрее, чем сортирующие сравнения. Вы отказываетесь от этого преимущества, если фактически удаляете их.
Will Ness 20.09.2012 03:41:58

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

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

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

2
10.08.2008 18:26:43

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

0
10.08.2008 19:58:38

@theprise

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

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

0
10.08.2008 20:24:01

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

-1
23.05.2017 12:33:26

вопрос @ 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;
    }
}
2
11.08.2008 01:42:41

Аспирант 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
11.08.2008 05:36:32

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

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

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

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

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

3
28.10.2008 06:30:04