Sito Atkina

Sito Atkina (nazywane też sitem Atkina-Bernsteina) – algorytm autorstwa A.O.L. Atkina i D.J. Bernsteina służący do wyszukiwania liczb pierwszych w dużych przedziałach. Metoda działa podobnie, jak sito Eratostenesa, jednak dzięki wykorzystaniu bardziej wyrafinowanej teorii jest szybsza i wymaga znacznie mniej pamięci.

Złożoność czasowa

Sito Atkina-Bernsteina znajduje (wypisuje) wszystkie liczby pierwsze mniejsze, niż $N$ w czasie O(N/log log N) i pamięci O(N^1/2+o(1)).

Zobacz też

• Liczby pierwsze
• Daniel J. Bernstein
• Sito Eratostenesa
• Sito Galwaya

Literatura

• A.O.L. Atkin, D.J. Bernstein, Prime Sieves Using Binary Quadratic Forms, 1999

Linki zewnętrzne

• Artykuł opisujący algorytm oraz jego implementację