Является ли Sieve of erathosthens лучшим алгоритмом для генерации простых чисел от 1 до N?
Мне задали этот вопрос в интервью. Я реализовал алгоритм, используя концепцию сита эратосфена и массив.
Есть ли лучший способ обойти этот вопрос Для тех, кто не знает сита, вот ссылка:
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
РЕДАКТИРОВАТЬ: Лучший с точки зрения времени и пространства сложности. Я только что сказал им, что недостаток SoE - космическая сложность. Поэтому они спросили меня, могу ли я что-нибудь с этим сделать. Вот как проходило интервью: 1) Реализовать алгоритм, который печатает простые числа от 1 до n. Ответ: Я использую SoE. 2) Это лучший способ сделать это. Ответ:???
2 ответа
Ну, это зависит от того, что вы подразумеваете под "лучшим". Сито Эратосфена очень легко внедрить, но Сито Аткина даст вам значительно лучшую производительность.
Таким образом, если "лучшее" означает простое в реализации и понимании, Эратосфен - путь. Если "лучший" означает, что вы хотите продемонстрировать свои навыки математика или иметь очень быстрый алгоритм, Atkin - это то, что вам нужно.
Ну, это зависит только от значения N:
Сито Эратосфена (простое сито) является одним из наиболее эффективных алгоритмов для нахождения всех простых чисел, меньших n, когда n меньше 10 миллионов (означает 10^7), поскольку простое сито требует O(n) линейного пространства. И мы знаем, что мы можем создать глобальный массив максимального размера 10^7. Таким образом, когда n больше 10^7, возникает проблема с простыми ситами, поскольку массив размером более 10 ^ 7 может не помещаться в памяти.
Для n>=10^7 мы можем использовать Сегментированное сито из Эратосфена, потому что в сегментированном сите мы можем улучшить потребление памяти от линейного до O(√n) пространства.
Обратите внимание, что временная сложность сегментированного сита такая же, как у простого сита. Единственное преимущество, которое имеют сегментированное сито: оно идеально подходит для больших "n"
Для интервью по программированию нет:). Хотя есть и это http://en.wikipedia.org/wiki/Sieve_of_Atkin и я уверен, что есть, вероятно, исследовательские работы, в которых можно найти небольшие оптимизации.