Prvočísla (kalkulačka)

Kalkulačka prvočísel je nástroj, ktorý mám pomôže zistiť, či:

je číslo prvočíslo,
nájde všetky prvočísla v zadanom intervale,
určí konkrétne prvočíslo podľa jeho poradia.

Je číslo prvočíslo?

Zoznam prvočísel v intervale

Nájdi prvočíslo podľa poradia

Čo je prvočíslo

Prirodzené čísla väčšie ako 1, ktoré majú práve dva rôzne delitele, číslo 1 a samo seba, nazývame prvočísla.

Prvočísla sú napr.: 2, 3, 5, 7, 11, atď.

Prirodzené čísla väčšie ako 1, ktoré majú viac ako dva rôzne delitele, nazývame zložené čísla.

Zložené čísla sú napr.: 4, 6, 8, 9, 10, 12 atď.

Číslo jedna nie je prvočíslo ani zložené číslo. Definícia hovorí, že prvočíslo je prirodzené číslo väčšie ako 1, ktoré je deliteľné číslami 1 a samo sebou (a zložené číslo má viac ako dvoch deliteľov). Keďže jednotka má len jedného deliteľa (sama seba), nespĺňa podmienku pre prvočíslo ani pre zložené číslo.

Číslo nula rovnako nie je prvočíslo ani zložené číslo, pretože:

nula nie je väčšie ako 1,
je deliteľná všetkými číslami (1, 2, 3, ….),
sama nula nič nedelí okrem seba (nula delené čokoľvek je stále 0, ale nie je definovaný opak)

Tabuľka prvočísel do 100 – kompletný prehľad prvočísel

V tabuľke nižšie môžeme nájsť prehľad prvočísel od 2 do 100 v prehľadnej tabuľkovej forme pre jednoduchú orientáciu a použitie.

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

Tabuľka prvočísel od 2 do 100. Zdroj: Vlastné spracovanie.

Využitie prvočísel

Prvočísla zohrávajú dôležitú úlohu v mnohých oblastiach matematiky, vedy a techniky. Ich jedinečné vlastnosti ich robia nenahraditeľnými v rôznych praktických aplikáciách:

prvočísla sú základom moderných šifrovacích metód, ako je napríklad RSA. Veľké prvočísla používame na vytváranie bezpečných kľúčov, ktoré chránia naše online komunikácie, internetové bankovníctvo či elektronický podpis,
testovanie prvočísel a generovanie náhodných čísel sú dôležité pre tvorbu efektívnych algoritmov, ktoré používame v rôznych oblastiach od simulácií až po hry,
sú základnými stavebnými kameňmi prirodzených čísel, pretože každé číslo sa dá jednoznačne rozložiť na súčin prvočísel. Táto vlastnosť je základom mnohých matematických dôkazov a štúdií,
prvočísla objavujeme aj v prírode, napríklad v štruktúrach rastlín alebo v rytmických vzoroch v hudbe a umení. Ich tajomná distribúcia inšpiruje vedcov a umelcov po celé stáročia.

História prvočísel

Prvý známy systematický výskum prvočísel pochádza od Euklida, jedného z najvýznamnejších matematikov staroveku. Jeho dielo „Základy“ (Elements), napísané okolo roku 300 pred n. l., obsahuje dôkaz o nekonečnom množstve prvočísel.

„Existuje viac ako akýkoľvek daný počet prvočísel.“

Toto je jeden z najznámejších dôkazov v matematike — elegantný a jednoduchý. Euklides dokázal, že ak by bolo prvočísel konečné množstvo, môžeme vytvoriť nové číslo, ktoré nie je deliteľné žiadnym z nich, čím dospejeme k sporu (teda dôkaz sporom).

Mersennove prvočísla

Mersennovo prvočíslo je prvočíslo špeciálneho tvaru, ktoré môžeme zapísať takto:

M_p = 2^p – 1

Kde p je tiež prvočíslo.

Príklad: Ak vezmeme, že p = 5, ktoré je prvočíslo, potom:

M₅ = 2⁵ – 1 = 32 – 1 = 31.

Je 31 prvočíslo? Áno, 31 je prvočíslo, pretože ho delia iba čísla 1 a 31. Môžeme povedať, že 31 je Mersennovo prvočíslo.

Avšak Mersennových čísel bolo objavených do 12. októbra 2024 presne 52 v poradí. V desiatkovej sústave obsahuje 41 024 320 číslic a zároveň toto je najvyššie známe prvočíslo. Je výsledkom výrazu 2^{136 279 841} – 1.

Ako testujeme, či číslo je prvočíslo

Na overenie, či je číslo prvočíslo, existuje viacero metód. Líšia sa svojou zložitosťou, rýchlosťou a vhodnosťou podľa veľkosti čísel.

Delenie

Snažíme sa deliť dané číslo všetkými číslami, ktoré sú väčšie ako 1 a zároveň menšie, nanajvýš rovné druhej odmocniny daného čísla; (alebo len prvočíslami) a sledujeme, či je niektoré z nich deliteľné bezo zvyšku.

Príklad: Zisťujeme, či je 29 prvočíslo:

Riešenie: Delíme číslo 29 prvočíslami: 2, 3, 5, … – nič z toho ho nedelí bezo zvyšku -> je to prvočíslo.

Táto metóda je vhodná pre pomerne malé čísla.

Eratosthenovo sito

Je to staroveká metóda, ktorá systematicky „vyraďuje“ násobky každého prvočísla zo zoznamu čísel. Zvyšné čísla sú prvočísla.

Príklad: Pre nájdenie prvočísel medzi prvými 20 číslami:

Riešenie:

1. krok: Zoznam obsahuje všetky čísla v rozsahu 2–20:
- Zoznam: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
2. krok: Odoberieme prvé číslo zo zoznamu a označíme ho ako prvočíslo:
- Známe prvočísla: 2
- Zoznam: 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
3. krok: Odoberieme zo zoznamu všetky násobky práve odobratého prvočísla:
- Známe prvočísla: 2
- Zoznam: 3 5 7 9 11 13 15 17 19
4. krok: Pokračujeme opäť bodom 2, pokiaľ ostávajú nejaké čísla:
- Známe prvočísla: 2 3
- Zoznam: 5 7 11 13 17 19
- Známe prvočísla: 2 3 5
- Zoznam: 7 11 13 17 19
- 5 je vyšší než √19, takže ostávajú už iba prvočísla.
Výsledný zoznam prvočísel v rozsahu 2–20: 2, 3, 5, 7, 11, 13, 17, 19.

Vhodný je pre nájdenie všetkých prvočísel v danom rozsahu, napr. do 10 000.

Miller–Rabinov test – pravdepodobnostný test

Namiesto overovania deliteľnosti testuje matematické vlastnosti prvočísel pomocou modulárnej aritmetiky. Je rýchly a efektívny aj pri veľmi veľkých číslach.

Výsledok nie je 100 % istý, ale s viacerými opakovaniami je pravdepodobnosť omylu extrémne malá.

Vhodný je pre veľmi veľké čísla (napr. stovky alebo tisíce cifier), často ho používame v kryptografii.

AKS test

AKS test (Agrawal–Kayal–Saxena) definitívne povie, či je číslo prvočíslo, bez pravdepodobnostných prvkov.

Je založený na matematickej vlastnosti, že:

(x – 1)ⁿ ≡ (xⁿ – 1) mod n

platí len pre prvočísla (v určitých podmienkach).

Výhodou je, že garantuje správny výsledok, no je napr. pomalší ako Miller-Rabinov test.

AKS test je vhodný pre matematické dôkazy, kde je nevyhnutná 100 % istota.

Často kladené otázky (FAQ)

Čo znamená, že číslo je deliteľné?

Ak môžeš číslo rozdeliť (vydeliť) iným číslom bez zvyšku, hovoríme, že je tým číslom deliteľné. Napríklad 10 je deliteľné číslom 5, pretože 10 ÷ 5 = 2 bez zvyšku.

Môže byť záporné číslo prvočíslom?

Nie. Prvočísla sú vždy kladné celé čísla väčšie ako 1.

Ktoré je najmenšie prvočíslo?

Najmenšie prvočíslo je 2. Je to tiež jediné párne prvočíslo.

Používajú sa prvočísla v šifrovaní?

Áno. Moderné šifrovacie algoritmy, ako RSA, využívajú veľké prvočísla na zabezpečenie dát. Dekompozícia veľkého čísla na prvočísla je výpočtovo náročná, čo zvyšuje bezpečnosť.

Existujú medzi prvočíslami nejaké vzory alebo pravidelnosti?

Prvočísla sa zdajú byť rozmiestnené náhodne, ale matematika objavila isté vzory – napríklad dvojice tzv. prvočíselných dvojičiek (napr. 11 a 13). Stále však neexistuje všeobecný vzorec, ktorý by generoval iba a všetky prvočísla.

Prečo sa prvočísla používajú na testovanie výkonu počítačov?

Pretože overovanie a hľadanie veľkých prvočísel si vyžaduje veľa výpočtovej sily a pamäte. Sú tak ideálne pre benchmarky a testovanie superpočítačov.

Existuje najväčšie známe prvočíslo?

Áno, ale stále sa hľadajú väčšie. Väčšinou ide o tzv. Mersennove prvočísla. Najväčšie nájdené je 2^{136 279 841} – 1.

Majú prvočísla praktické využitie aj mimo matematiky a informatiky?

Áno, napríklad v biologických modeloch (napr. životný cyklus niektorých druhov cikád), v kryptografii v komunikácii, či pri generovaní náhodných čísel.

Zdroje:

ČERETKOVÁ, Soňa – ŠEDIVÝ, Ondrej – TEPLIČKA, Ivan. matematika pre 7.ročník základnej školy a 2. ročník gymnázia s osemročným štúdiom. Prvé vydanie Bratislava: Mladé letá, 2022. 96 s. ISBN 978-80-10-03882-4
Euclid’s elements – Book IX,Proposition 20: https://mathcs.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html
Provčíslo: https://sk.wikipedia.org/wiki/Prvo%C4%8D%C3%ADslo
Mersennovo prvočíslo: https://sk.wikipedia.org/wiki/Mersennovo_prvo%C4%8D%C3%ADslo
Eratostenovo sito: https://sk.wikipedia.org/wiki/Eratostenovo_sito