Sito Atkina
Z Wikipedii
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.
[edytuj] 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(N1/2+o(1)).
[edytuj] Literatura
- A.O.L. Atkin, D.J. Bernstein, Prime Sieves Using Binary Quadratic Forms, 1999
[edytuj] Zobacz też
- Liczby pierwsze
- Daniel J. Bernstein
- Sito Eratostenesa
- Sito Galwaya