Sieve of erathosthens - лучший алгоритм для генерации простых чисел от 1 до N?

Question

Мне задали этот вопрос в интервью.Я реализовал алгоритм, используя концепцию сита из эратосфена и массив.

Есть ли лучший способ обойти этот вопрос Для тех, кто не знает сита, вот ссылка:

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

РЕДАКТИРОВАТЬ: Лучший с точки зрения времени и пространства сложности.Я только что сказал им, что недостаток SoE - космическая сложность.Поэтому они спросили меня, могу ли я что-нибудь с этим сделать.Вот как проходило интервью: 1) Реализовать алгоритм, который печатает простые числа от 1 до n. Ответ: Я использую SoE. 2) Это лучший способ сделать это. Ответ: ???

Answer 1

Ну, это зависит от того, что вы подразумеваете под «лучшим». Сито Эратосфена очень легко реализовать, но Сито Аткина даст вам значительно лучшую производительность.

Так что, если «лучшее» означает простое в реализации и понимании, Эратосфен - путь. Если «лучший» означает, что вы хотите продемонстрировать свои навыки математика или имеете очень быстрый алгоритм, Аткин - это то, что вам нужно.

Answer 2

Ну, это зависит только от значения N:

• Сито Эратосфена (Простое сито) является одним из наиболее эффективных алгоритмов для нахождения всех простых чисел, меньших n, когда nменьше 10 миллионов (означает 10 ^ 7), потому что простое сито требует O (n) линейного пространства.И мы знаем, что мы можем создать глобальный массив максимального размера 10 ^ 7.Таким образом, когда n больше 10 ^ 7, возникает проблема с простыми ситами, поскольку массив размером более 10 ^ 7 может не помещаться в памяти.

• Для n> = 10 ^ 7 мы можем использовать Сегментированное сито из эратосфена , поскольку в сегментированном сите мы можем улучшить потребление памяти с линейного до O(√n) пробел.

Обратите внимание, что временная сложность сегментированного сита такая же, как у простого сита.Единственное преимущество, которым обладают сегментированные сита: оно идеально подходит для больших 'n'

Answer 3

Для интервью по программированию нет :). Хотя есть это http://en.wikipedia.org/wiki/Sieve_of_Atkin, и я уверен, что есть, вероятно, исследовательские работы, которые предлагают небольшие оптимизации.