Algoritmy na hľadanie prvočísel
Existujú 4 algoritmy na hľadanie prvočísel, uvádzam len 3 najznámejšie z nich.
1. Eratostenovo sito
Eratostenovo sito je jednoduchý algoritmus pre nájdenie všetkých prvočísel menších ako zadaná horná hranica. Algoritmus je pomenovaný po gréckom matematikovi Eratostenovi, ktorý žil v rokoch 276–194 pred Kr.
Algoritmus funguje na postupnom „presievaní“ zoznamu čísel – na začiatku zoznam obsahuje všetky čísla v danom rozsahu (2, 3, 4, …, zadané maximum). Potom sa opakovane prvé číslo zo zoznamu vyberie, toto číslo je prvočíslom; zo zoznamu sa potom odstránia všetky jeho násobky (to sú zložené čísla). Tak sa pokračuje až dovtedy, kým sa zo zoznamu neodstráni posledné číslo (alebo dovtedy, keď je ako prvočíslo označené číslo vyššie ako odmocnina najvyššieho čísla – v tomto prípade všetky zostávajúce čísla v zozname sú určite prvočísla).
2. Atkinovo sito
V matematike, je Atkinovo sito rýchly a moderný algoritmus pre nájdenie všetkých prvočísel až do určeného celého čísla. Je to optimalizovaná verzia starého Eratosthenovho sita. Atkinovo sito bolo vytvorené v roku 2004 Arthurom Oliverom Lonsdalemom Atkinom a Danielom Juliusom Bernsteinom.
3. Sundaramovo sito
Sundaramovo sito je tvorené nekonečným počtom aritmetických postupností. Každý člen prvej rady je zároveň prvým členom jednej z ďalších rád. Rozdielmi v jednotlivých radách sú postupne všetky nepárne čísla počínajúc trojkou. Platí, že ak je číslo n obsiahnuté v tejto tabuľke, potom je číslo 2n +1 zložené. Naopak ak nie je číslo n obsiahnuté v tejto tabuľke, je číslo 2n + 1 prvočíslo. Napríklad číslo 7 sa nachádza v tabuľke, platí teda 2 · 7 + 1, tj. číslo 15 je číslo zložené. Číslo 5 sa v tabuľke nenachádza, platí teda 2 · 5 + 1, tj. číslo 11 je prvočíslo.