b'\n_START_ARTICLE_\nSito Atkina\n_START_PARAGRAPH_\nSito Atkina (nazywane te\xc5\xbc sitem Atkina-Bernsteina) \xe2\x80\x93 algorytm autorstwa A.O.L. Atkina i D.J. Bernsteina s\xc5\x82u\xc5\xbc\xc4\x85cy do wyszukiwania liczb pierwszych w du\xc5\xbcych przedzia\xc5\x82ach. Metoda dzia\xc5\x82a podobnie, jak sito Eratostenesa, jednak dzi\xc4\x99ki wykorzystaniu bardziej wyrafinowanej teorii jest szybsza i wymaga znacznie mniej pami\xc4\x99ci.\n_START_SECTION_\nOpis dzia\xc5\x82ania\n_START_PARAGRAPH_\nAlgorytm ca\xc5\x82kowicie pomija wszystkie liczby podzielne przez 2, 3 lub 5. Wszystkie liczby z parzyst\xc4\x85 reszt\xc4\x85 z dzielenia przez 60 s\xc4\x85 podzielne przez 2 i nie s\xc4\x85 pierwsze. Wszystkie liczby z reszt\xc4\x85 z dzielenia przez 60 podzieln\xc4\x85 przez 3 s\xc4\x85 tak\xc5\xbce podzielne przez 3 i nie s\xc4\x85 pierwsze. Wszystkie liczby z reszt\xc4\x85 z dzielenia przez 60 podzieln\xc4\x85 przez 5 s\xc4\x85 tak\xc5\xbce podzielne przez 5 i nie s\xc4\x85 pierwsze. Wszystkie te reszty s\xc4\x85 pomijane._NEWLINE_Wszystkie liczby n z reszt\xc4\x85 z dzielenia przez 60 wynosz\xc4\x85c\xc4\x85 1, 13, 17, 29, 37, 41, 49 lub 53 maj\xc4\x85 reszt\xc4\x99 z dzielenia przez 4 r\xc3\xb3wn\xc4\x85 1. Te liczby s\xc4\x85 pierwsze wtedy i tylko wtedy, gdy liczba rozwi\xc4\x85za\xc5\x84 wielomianu 4x\xc2\xb2 + y\xc2\xb2 = n jest nieparzysta i niepodzielna przez kwadraty liczb ca\xc5\x82kowitych._NEWLINE_Wszystkie liczby n z reszt\xc4\x85 z dzielenia przez 60 wynosz\xc4\x85c\xc4\x85 7, 19, 31 lub 43 maj\xc4\x85 reszt\xc4\x99 z dzielenia przez 6 r\xc3\xb3wn\xc4\x85 1. Te liczby s\xc4\x85 pierwsze wtedy i tylko wtedy, gdy liczba rozwi\xc4\x85za\xc5\x84 wielomianu 3x\xc2\xb2 + y\xc2\xb2 = n jest nieparzysta i niepodzielna przez kwadraty liczb ca\xc5\x82kowitych._NEWLINE_Wszystkie liczby n z reszt\xc4\x85 z dzielenia przez 60 wynosz\xc4\x85c\xc4\x85 11, 23, 47 lub 59 maj\xc4\x85 reszt\xc4\x99 z dzielenia przez 12 r\xc3\xb3wn\xc4\x85 11. Te liczby s\xc4\x85 pierwsze wtedy i tylko wtedy, gdy liczba rozwi\xc4\x85za\xc5\x84 wielomianu 3x\xc2\xb2 - y\xc2\xb2 = n jest nieparzysta i niepodzielna przez kwadraty liczb ca\xc5\x82kowitych._NEWLINE_\xc5\xbbadna z potencjalnych liczb pierwszych nie jest podzielna przez liczby 2, 3 i 5, wi\xc4\x99c nie mo\xc5\xbce by\xc4\x87 podzielna r\xc3\xb3wnie\xc5\xbc przez ich kwadraty. Dlatego sprawdzenie czy rozwi\xc4\x85zania wielomian\xc3\xb3w nie jest podzielne przez kwadraty liczb ca\xc5\x82kowitych nie zawiera 2\xc2\xb2, 3\xc2\xb2 i 5\xc2\xb2.\n_START_SECTION_\nZ\xc5\x82o\xc5\xbcono\xc5\x9b\xc4\x87 obliczeniowa\n_START_PARAGRAPH_\nSito Atkina-Bernsteina znajduje (wypisuje) wszystkie liczby pierwsze mniejsze ni\xc5\xbc N w czasie O(N) wykorzystuj\xc4\x85c pami\xc4\x99\xc4\x87 O(N1/2/log N).'