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.

Opis działania

Algorytm całkowicie pomija wszystkie liczby podzielne przez 2, 3 lub 5. Wszystkie liczby z parzystą resztą z dzielenia przez 60 są podzielne przez 2 i nie są pierwsze. Wszystkie liczby z resztą z dzielenia przez 60 podzielną przez 3 są także podzielne przez 3 i nie są pierwsze. Wszystkie liczby z resztą z dzielenia przez 60 podzielną przez 5 są także podzielne przez 5 i nie są pierwsze. Wszystkie te reszty są pomijane.

Wszystkie liczby n z resztą z dzielenia przez 60 wynoszącą 1, 13, 17, 29, 37, 41, 49 lub 53 mają resztę z dzielenia przez 4 równą 1. Te liczby są pierwsze wtedy i tylko wtedy, gdy liczba rozwiązań wielomianu 4x2 + y2 = n jest nieparzysta i niepodzielna przez kwadraty liczb całkowitych.

Wszystkie liczby n z resztą z dzielenia przez 60 wynoszącą 7, 19, 31 lub 43 mają resztę z dzielenia przez 6 równą 1. 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.

Wszystkie liczby n z resztą z dzielenia przez 60 wynoszącą 11, 23, 47 lub 59 mają resztę z dzielenia przez 12 równą 11. 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 2², 3² i 5².

Złożoność obliczeniowa

Sito Atkina-Bernsteina znajduje (wypisuje) wszystkie liczby pierwsze mniejsze niż N w czasie O(N) wykorzystując pamięć O(N^1/2/log N).

Zobacz też

• Liczby pierwsze
• Daniel J. Bernstein
• Sito Eratostenesa

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ę. edu.i-lo.tarnow.pl. [zarchiwizowane z tego adresu (2015-07-16)].