Te liczby są pierwsze wtedy i tylko wtedy, gdy liczba rozwiązań wielomianu 3x2 - y2 = n jest nieparzysta i niepodzielna przez kwadraty liczb całkowitych.
Żadna z potencjalnych liczb pierwszych nie jest podzielna przez liczby 2, 3 i 5, więc nie może być podzielna również przez ich kwadraty. Dlatego sprawdzenie czy rozwiązania wielomianów nie jest podzielne przez kwadraty liczb całkowitych nie zawiera 22, 32 i 52.
Złożoność obliczeniowa Sito Atkina-Bernsteina znajduje (wypisuje) wszystkie liczby pierwsze mniejsze niż N w czasie O(N) wykorzystując pamięć O(N1/2/log N).
Literatura A.O.L. Atkin, D.J. Bernstein, Prime Sieves Using Binary Quadratic Forms, 1999
Linki zewnętrzne
Kategoria:Algorytmiczna teoria liczb