Реализации алгоритмов/Решето Аткина: различия между версиями

'''Решето́ А́ткина''' — метод нахождения всех [[w:Простое число|простых чисел]], не превышающих заданное натуральное ''limit''. В отличие от [[Реализации алгоритмов/Решето Эратосфена|решета Эратосфена]], последовательно исключающего числа, кратные уже найденным простым, данный алгоритм производит предварительное просеивание, а затем из найденных чисел исключает кратные квадратам простых, благодаря чему имеет теоретически лучший показатель асимптотической сложности <math>\mathop O(\frac{1}{\log \log (limit)})</math>.

 

}

</source>

 

=Ссылки=