- Liczba Pierwsza dzieli się przez 1 i samą siebie.
- Liczba pierwsza jest liczbą nieparzystą zakończoną cyframi 1,3,7 lub 9.
- Przy szukaniu Liczby Pierwszej bierzemy pod uwagę wszystkie liczby nieparzyste oprócz tych z końcówką 5.
- Tutaj najważniejsze: Istnieje wspólny związek między daną liczbą a sumą jej cyfr dzięki czemu nie musimy sprawdzać każdej liczby nieparzystej tylko te,które trzeba sprawdzić.
O, zobacz, 9 to liczba pierwsza - zgodne z punktem 1 (nieparzysta i dzieli się przez 1 i samą siebie), 2 (kończy się cyfrą 9), 3 (nie kończy się cyfrą 5) i 4 (istnieje związek między tą liczbą a sumą jej cyfr, więc trzeba sprawdzić tę liczbę tylko jeśli trzeba ją sprawdzić).
Z kolei liczba 5 nie jest liczbą pierwszą, bo kończy się na 5... Wait... What?
A teraz na serio: złożoność obliczeniową sita Eratostenesa możesz znaleźć w sieci, ale ułatwię Ci: O(n * log(n) * log(log(n))). Złożoność obliczeniowa AKS to O(log12(n)).
Teraz znajdź takie n, dla którego log11(n) = n * log(log(n)), będziesz miał graniczną wartość, dla złożoność jest podobna.
W praktyce da Ci to tylko orientacyjną wartość, bo złożoność obliczeniowa pokazuje tylko przyrost obliczeń, nie pokazując ile kosztuje ich jednostka. A więc może się okazać, że konkretna implementacja sita będzie sto razy tańsza od konkretnej implementacji AKS, przez co pomylisz się o np. rząd wielkości. Albo cztery.
Ale najpierw proponuję, żebyś zobaczył, co to jest to AKS, bo jak nie kumasz metod probabilistycznych, to krzywe eliptyczne mogą okazać się jeszcze trudniejsze.