сообщая все простые числа меньше чем n

Question

Мне нужно напечатать все простые числа меньше заданного числа n.Я могу использовать сито Eratothenes, но время работы этого алгоритма НЕ O (n).Есть ли какое-либо время (n) для решения этой проблемы?

Answer 1

Сито Эратосфена имеет временную сложность O (n log log n). Функция log log n растет очень медленно; например, log (log (10 ^ 9)) = 3. Это означает, что вы можете эффективно трактовать журнал log n как часть сложности времени как константу и игнорировать ее, давая временную сложность «почти» O (n) .

Существуют различные алгоритмы, которые работают во времени O (n) или O (n / log log n), включая сита колеса Притчарда и сито Аткинса. Но постоянные факторы обычно делают эти алгоритмы медленнее на практике, чем сито Эратосфена. Если вам не нужна чрезвычайная скорость, и вы не знаете, что делаете, и вы готовы тратить на это много времени, практический ответ - это Сито Эратосфена.

Ваш вопрос говорит о том, что вы собираетесь напечатать список простых чисел. В этом случае выходные данные будут доминировать во время выполнения любого выбранного вами алгоритма. Поэтому сделайте себе одолжение и внедрите простое Сито Эратосфена.

Answer 2

Я не думаю, что вы найдете алгоритм для проверки произвольного числа на простоту с O (n) временной сложностью.Я почти уверен, что АНБ (и любые другие организации, занимающиеся проблемами криптографии) не были бы очень довольны этим: -)

Единственный способ получить O (n) или лучший способнапример, нужно предварительно рассчитать (например) первые пятьдесят миллионов простых чисел (или использовать чей-то уже предварительно рассчитанный список ) и использовать его в качестве поиска.У меня есть такой файл локально, и просто запустить grep поверх него, чтобы посмотреть, простое ли число.Для произвольных чисел это не помогает, но мне редко приходится использовать такие большие.Крипто-парни, конечно, сочтут такой список чрезвычайно маленьким для своих целей.

И, если вы превратите его в растровое изображение (около 120M для первых пятидесяти миллионов простых чисел), вы даже можете уменьшить сложность.в O (1), просто превратив число в байтовое смещение и битовую маску - пару битовых сдвигов и / или битовых операций.

Однако, получая список простых чисел нижеопределенная n определенно выполнима в O (n) временной сложности. Бумага Аткина и Бернштейна , детализирующая Сито Аткина утверждает:

Мы вводим алгоритм, который вычисляет простые числа до N, используя O(N/log(log(N))) сложения...

, что на самом деле немного лучше , чем O (n).

Тем не менее, оно вряд ли будет конкурировать с поисковым решением.Мой совет - использовать Аткина или Эратосфена для составления списка - это не имеет значения, поскольку вы будете делать этот бит один раз , поэтому производительность не будет критичной.

Тогдаиспользуйте сам список для проверки простоты.