Prvočíslo - jsou to přirozená čísla, která mají pouze dva dělitele: 1 a samotné číslo. Jejich zvláštností je absence jiných dělitelů. Prvočísla jsou jedním z hlavních předmětů studia v matematice a jsou důležitá v různých oblastech vědy a techniky.
Jak ale zjistit, zda je dané číslo jednoduché?
Existuje několik metod, kterými lze určit jednoduchost čísla n. jedním z nejjednodušších a nejúčinnějších způsobů je kontrola dělitelů čísla. K tomu je nutné postupně dělit číslo n na všechna přirozená čísla od 2 do druhé odmocniny z n.pokud je výsledkem dělení přirozené číslo, pak je číslo n složené a má jiné faktory než 1 a samotné číslo n. Pokud žádné z čísel před druhou odmocninou z n není dělitelem tohoto čísla, pak číslo n je prvočíslo.
Příklad:
Řekněme, že musíme zjistit, zda je číslo 17 prvočíslo. Vypočítáme druhou odmocninu z čísla 17. Bude zaokrouhlen na 4. Nyní zkontrolujeme děliče 17: 2, 3, 4. Žádné z těchto čísel není dělitelem čísla 17. Číslo 17 je tedy prvočíslo.
Co je prvočíslo přírodního čísla?
Prvočísla jsou základem pro různé matematické operace a algoritmy. Používají se například v kryptografii k vytváření šifer a ochraně informací.
Prvočísla mají řadu zajímavých vlastností a vlastností. Například nekonečno množiny prvočísel je stále jedním z nevyřešených problémů v matematice.
Definice prvočísel a jejich vlastností hraje důležitou roli v různých oblastech vědy a techniky. Porozumění a používání prvočísel pomáhá řešit různé úkoly a vyvíjet nové algoritmy a modely.
Definice prvočísla
Existuje několik způsobů, jak zjistit, zda je číslo jednoduché nebo složené:
- Metoda dělení: jsou testována všechna čísla od 2 do kořene z čísla n. Pokud je alespoň jedno z těchto čísel dělitelem n, pak je číslo n složené. V opačném případě je číslo n prvočíslo.
- Metoda přesouvání: všechna čísla od 2 do n-1 se přepočítají a zkontroluje se, zda je číslo n beze zbytku dělitelné. Pokud je dělitelné, pak je číslo n složené, jinak je prvočíslo.
- Metoda eratosfénové mřížky: vytvoří se pole o délce n a vyplní se hodnotami od 2 do n. poté se od prvního prvku každé prvočíslo stane "označeným" a všechna čísla, která se na něj beze zbytku dělí, jsou označena jako složená. Když jsou všechna čísla zpracována, zbývající neoznačená čísla jsou jednoduchá.
Použití různých metod závisí na konkrétním úkolu a požadavcích na výkon. Výběr metody se může lišit v závislosti na velikosti čísla a dostupných výpočetních zdrojích.
Jak zkontrolovat jednoduchost přirozeného čísla?
- Metoda přebírání dělitelů: pro každé přirozené číslo k v intervalu 2 až n-1 zkontrolujeme, zda je n vyděleno k beze zbytku. Pokud je dělitel nalezen, pak číslo n není prvočíslo.
- Metoda kontroly k odmocnině: pokud n nemá děliče v intervalu 2 až odmocniny n, je to jednoduché. Pokud by n mělo dělitel větší než druhá odmocnina z n, mělo by také dělitel menší než druhá odmocnina z n, což je v rozporu s ověřováním dělitelů.
- Millerův-Rabinův test: je to pravděpodobnostní algoritmus, který umožňuje s vysokou pravděpodobností ověřit jednoduchost čísla n. Je založen na teorii čísel a modulární aritmetice.
Pomocí jedné z těchto metod lze určit, zda je dané přirozené číslo jednoduché nebo složené.
Příliš dělitelů čísel
Přepočet dělitelů čísel lze provést pomocí cyklu. Začněte cyklus číslem 2 a zvyšte jej o 1 na každou iteraci na n-1.
V rámci cyklu zkontrolujeme, zda je číslo n vyděleno aktuální hodnotou cyklu beze zbytku. Pokud je dělitelné, číslo n má dělitel a není prvočíslo.
Pokud cyklus končí bez nalezení dělitele, pak je číslo n prvočíslo.
Wilsonova Věta
Toto tvrzení formuloval v roce 1770 skotský matematik John Wilson, i když věřil, že tuto větu objevil Lotyšský matematik Leonard Euler ještě před ním. Wilsonova věta je poměrně jednoduché pravidlo, které umožňuje určit jednoduchost přirozeného čísla, aniž byste jej museli kontrolovat na dělitele.
Příklad: Řekněme, že musíme zkontrolovat, zda je číslo 7 prvočíslo. Podle Wilsonovy věty je třeba počítat (7-1)! + 1 = 6! + 1 = 720 + 1 = 721. Pokud je výsledné číslo dělitelné 7 beze zbytku, pak je číslo 7 prvočíslo. V tomto případě, 721 není dělitelné 7 beze zbytku, takže 7 není prvočíslo.
Algoritmy pro určování prvočísel
Existuje několik algoritmů, které umožňují určit, zda je číslo prvočíslo:
| Algoritm | Popis |
|---|---|
| Naivní | Kontroluje dělitelnost čísla na všechny hodnoty od 2 do n-1. Pokud je alespoň jedno číslo, na které je číslo vyděleno beze zbytku, není to jednoduché. |
| Eratosthen | Umožňuje najít všechna prvočísla v daném rozsahu. Algoritmus je založen na střídavém vyškrtnutí všech čísel násobků nalezených prvočísly. |
| Millerův-Rabinův Test | Složitější algoritmus, který je založen na pravděpodobnostní kontrole čísla na jednoduchost. Algoritmus kontroluje několik náhodných bází čísla a určuje, zda je prvočíslo s vysokou pravděpodobností. |
Výběr algoritmu pro stanovení prvočísel závisí na předpokládané velikosti čísla a požadované rychlosti práce. Pro malá čísla se obvykle používá naivní algoritmus, zatímco pro velká čísla je vhodnější použít složitější algoritmy.
Přemíra dělitelů
K určení prvočísla přírodního čísla n lze použít metodu přeměny dělitelů.
Přepočet dělitelů spočívá v ověření všech čísel od 2 do kořene čtverce od n K dělitelnosti s n. pokud žádné z těchto čísel nerozdělí n beze zbytku, pak je číslo n prvočíslo.
Pro efektivní přepojování děličů lze použít následující algoritmus:
- Zkontrolujte, zda je n roven 2 nebo 3. Pokud ano, číslo n je prvočíslo.
- Zkontrolujte, zda je n rozdělen na 2 nebo 3 beze zbytku. Pokud ano, číslo n není jednoduché.
- Zkontrolujte čísla od 5 do kořene čtverce od n v krocích po 6. Pokud je alespoň jedno z těchto čísel beze zbytku vyděleno, pak číslo n není prvočíslo.
- Zkontrolujte čísla od 7 do kořene čtverce od n v krocích po 6. Pokud je alespoň jedno z těchto čísel beze zbytku vyděleno, pak číslo n není prvočíslo.
- Pokud žádné z čísel nerozdělí n beze zbytku, pak je číslo n prvočíslo.
Pomocí přílišných dělitelů lze efektivně určit, zda je dané přirozené číslo prvočíslo.
Test Farma
Podstatou testu je ověření podmínky, která je důsledkem malé Fermatovy věty. Pokud číslo n splňuje podmínku, je s velkou pravděpodobností jednoduché.
Podmínku testu lze popsat následovně:
- Je vybráno náhodné číslo a, které je menší než n.
- Vypočítá se hodnota a^ podle modulu n.
- Pokud výsledek výpočtu není 1, pak číslo n není prvočíslo.
- Pokud je výsledek 1, číslo n může být jednoduché.
- Opakují se kroky 1-4 pro několik náhodných čísel a.
- Pokud je pro všechna čísla a výsledek 1, pak je číslo n s velkou pravděpodobností prvočíslo.
Test však není zcela spolehlivý a může přinést falešné výsledky, které ukazují složená čísla jako prvočísla a naopak. Test se proto častěji používá v kombinaci s jinými testy k dosažení přesnějších výsledků.