Kalkulačka prvočísel

Kalkulačka prvočísel - součet, počet a hledání prvočísel

🔢 Spočítejte součet prvočísel, najděte prvočísla v rozsahu, ověřte, zda je číslo prvočíslo, a určete n-té prvočíslo. Rychlý algoritmus Eratosthenova síta s vizualizací.

Co jsou prvočísla?

Prvočíslo je přirozené číslo větší než 1, které nelze vytvořit vynásobením dvou menších přirozených čísel. Jinými slovy má přesně dva dělitele: 1 a sebe sama.

Prvních 25 prvočísel

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Jak ověřit, zda je číslo prvočíslo

Metoda 1 - Zkoušení dělením:

• Zkontrolujte, zda je n dělitelné některým číslem od 2 do √n
• Pokud ano, je složené (není prvočíslo)
• Pokud ne, je prvočíslo

Příklad: Je 17 prvočíslo?

• √17 ≈ 4.12, proto zkoušíme dělitelnost 2, 3, 4
• 17 ÷ 2 = 8.5 (nedělitelné)
• 17 ÷ 3 = 5.67 (nedělitelné)
• 17 ÷ 4 = 4.25 (nedělitelné)
• Výsledek: 17 je prvočíslo!

Eratosthenovo síto

Starověký algoritmus pro nalezení všech prvočísel do n:

• Krok 1: Vypište všechna čísla od 2 do n
• Krok 2: Označte 2 jako prvočíslo a vyškrtněte všechny násobky 2
• Krok 3: Najděte další neoznačené číslo (3) a označte jej jako prvočíslo
• Krok 4: Vyškrtněte všechny násobky tohoto prvočísla
• Krok 5: Opakujte až do √n
• Výsledek: Všechna nevyškrtnutá čísla jsou prvočísla

Součet prvočísel

Součet prvních n prvočísel:

• Prvních 10 prvočísel: 2+3+5+7+11+13+17+19+23+29 = 129
• Prvních 100 prvočísel: součet = 24,133
• Prvních 1000 prvočísel: součet = 3,682,913

Součet prvočísel do n:

• Do 10: 2+3+5+7 = 17
• Do 100: součet = 1,060
• Do 1000: součet = 76,127

Věta o prvočíslech

Počet prvočísel menších než n je přibližně n/ln(n):

• Do 100: ~25 prvočísel (skutečně: 25)
• Do 1,000: ~145 prvočísel (skutečně: 168)
• Do 10,000: ~1,086 prvočísel (skutečně: 1,229)
• Do 100,000: ~8,686 prvočísel (skutečně: 9,592)

Typy prvočísel

Dvojčata prvočísla: Prvočísla, která se liší o 2

• (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)...

Mersennova prvočísla: Tvar 2ᵖ - 1, kde p je prvočíslo

• 2² - 1 = 3
• 2³ - 1 = 7
• 2⁵ - 1 = 31
• 2⁷ - 1 = 127
• Největší známé prvočíslo je Mersennovo (24,8 milionu číslic!)

Sophie Germainova prvočísla: Prvočíslo p, pro které je 2p+1 také prvočíslo

• 2 (2×2+1 = 5), 3 (2×3+1 = 7), 5 (2×5+1 = 11), 11, 23, 29...

Fermatova prvočísla: Tvar 2^(2ⁿ) + 1

• F₀ = 3, F₁ = 5, F₂ = 17, F₃ = 257, F₄ = 65,537
• Známo je pouze 5 Fermatových prvočísel

Využití prvočísel

Kryptografie (RSA):

• Je založena na obtížnosti rozkladu velkých čísel
• Využívá dvě velká prvočísla (stovky číslic)
• Zabezpečuje online bankovnictví, e-maily a weby

Hašovací tabulky:

• Hašovací tabulky s prvočíselnou velikostí snižují kolize
• Používají se v databázích a cache

Generování náhodných čísel:

• Prvočísla vytvářejí lepší pseudonáhodné posloupnosti
• Používají se v simulacích a hrách

Zajímavosti o prvočíslech

• Nekonečno: Dokázal Eukleidés ~300 př. n. l. – prvočísla nikdy nekončí
• Mezery: Mohou být libovolně velké (žádná prvočísla pro miliony po sobě jdoucích čísel)
• Goldbachova domněnka: Každé sudé číslo > 2 je součtem dvou prvočísel (neprokázáno!)
• Riemannova hypotéza: Milionová odměna za důkaz o rozložení prvočísel
• Mezery mezi prvočísly: Rozdíly mezi po sobě jdoucími prvočísly rostou
• Pravděpodobnost: Náhodné číslo n má přibližně 1/ln(n) šanci být prvočíslem

Rekordy

• Největší známé prvočíslo: 2^82,589,933 - 1 (objeveno 2018, 24,862,048 číslic)
• Největší dvojčata prvočísla: 2,996,863,034,895 × 2^1,290,000 ± 1
• Výpočty: GIMPS (Great Internet Mersenne Prime Search) distribuovaný projekt

Časté omyly

• 1 není prvočíslo: Podle moderní definice (musí mít přesně 2 dělitele)
• Ne všechna lichá čísla jsou prvočísla: 9, 15, 21, 25... jsou složená
• Vzorec pro všechna prvočísla: Neexistuje jednoduchý vzorec pro generování všech prvočísel
• Vzor v prvočíslech: Neexistuje předvídatelný vzor (působí náhodně)

💡 Tip: Při ověřování, zda je velké číslo prvočíslem, stačí testovat dělitelnost pouze do jeho odmocniny! Například pro 997 stačí zkoušet dělitele do √997 ≈ 31.6, tedy 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. Pokud žádný z nich nedělí 997 beze zbytku, je to prvočíslo. Tato optimalizace je velmi rychlá. Navíc, kromě 2 a 3, jsou všechna prvočísla tvaru 6k±1, což může hledání ještě urychlit!