Сравнение Sieve of Sundaram и Sieve of Atkin для генерации списка простых чисел

Question

Время работы "сита сундарама" для генерации списка простых чисел до числа n задано O (n * log (n)) по ссылке: http://en.wikipedia.org/wiki/Sieve_of_Sundaram. Этот алгоритм лучше чем «Сито Аткина», и если он немного уточнит, как именно это работает?

Answer 1

В теории:

• Сито Сундарама имеет арифметическую сложность O (n log n).
• Базовое сито Эратосфена имеет арифметическую сложность O (n log log n).
• Оптимизированные варианты сита Эратосфена имеют арифметическую сложность O (n).
• Сито Аткина имеет не только арифметическую, но и битовую сложность O (n / log log n).
• Магическое сито, где вам даны простые числа, по порядку, занимает время O (n / log n).

На практике сито Сундарама настолько медленное, что никто не использует его, а сито Аткина медленнее, чем оптимизированные варианты Эратосфена (хотя оно по крайней мере конкурентно). Возможно, однажды Аткин или что-то еще вытеснит Эратосфена, но это вряд ли произойдет в ближайшее время. (Кроме того, нет такой вещи, как магия.)

Answer 2

Ну, на странице Википедии для Сита Аткина написано:

Это сито вычисляет простые числа до N, используя операции O (N / log log N)

Это лучше, чем Сито Сундарама, которое operations (N log N) в операциях (обратите внимание, что это не O (N log N) - между O () и Θ (есть небольшая разница))).