Prvočísla
Prvočísla definujeme jako taková přirozená čísla, která jsou beze zbytku dělitelná pouze jedničkou a sebou samým.
Na obrázku vlevo je uvedeno prvních 25 prvočísel, které nalezneme v první stovce přirozených čísel. Prvočísla můžeme chápat jako základní kameny,
z nichž jsou poskládána všechna celá čísla. Každé přirozené číslo lze zapsast jako součin prvočísel, například:
30 = 2 x 3 x 5, nebo
245 = 5 x 7 x 7.
Tato čísla, která vznikla jako součin prvočísel, označujeme přívlastkem složená. Každé složené číslo lze jednoznačně rozložit na prvočísla. Tento fakt se označuje jako základní věta aritmetiky. Bylo dokázáno, že prvočísel je nekonečně mnoho. Ačkoliv se výskyt prvočísel jeví jako nahodilý, jsou známa určitá pravidla, podle kterých se výskyt provočísel řídí. Carl Friedrich Gauss zjistil, že hustota prvočísel se přibližně rovná 1/Ln(n), kde Ln je přirozený logaritmus čísla n. Uvedená funkce aproximuje podíl prvočísel menších než n: Dn = P(n)/n. Skutečné i odhadnuté podíly prvočísel (pro n od deseti do milionu) shrnuje následující tabulka.
Z tabulky je patrné, že s rostoucím n se odhad pomocí přirozeného logaritmu blíží skutečnému podílu prvočísel. Další větu popisující rozložení prvočísel přináší Bertrandův postulát, který říká, že pro každé přirozené číslo n>1 existuje prvočíslo p, pro které platí: n < p < 2n.
Dalším zajímavým tématem jsou prvočíselné dvojice. Jedná se o taková prvočísla, která se liší pouze o dvojku. Nejmenší takovou dvojící je pár 3 a 5. Naopak největší dosud objevenou dvojicí je 3 756 801 695 685 · 2666 669 - 1 a 3 756 801 695 685 · 2666 669 + 1. Předpokládá se, že prvočíselných dvojic je nekonečně mnoho, nicméně toto tvrzení dosud nebylo dokázáno.
Eratosthenovo síto
Eratosthenovo síto je jednoduchým algoritmem na hledání prvočísel v zadaném rozsahu. Síto prosívá prvočísla takto: Nejprve vypíšeme čísla od 2 do n. Dvojka je první prvočíslo, necháme ji na prvním místě našeho seznamu a odstraníme všechny její násobky. Dalším na řadě je číslo 3, necháme ji v seznamu a odstraníme všechny násobky trojky. Takto pokračujeme, dokud neodstraníme všechna složená čísla a v seznamu nám nezůstanou pouze prvočísla.
Komentáře k článku