Matematické Fórum

Skrblik · 05. 01. 2012 20:45

Dobrý den!
Jak se dá zjistit, zda je zadané číslo prvočíslem? Např. 2003. Hledal jsem na netu, ale našlo to jen nějaké algoritmy do PC. Nedá se to zjistit pomocí kalkulačky a hlavy?

Díky moc za rady!

vanok · 05. 01. 2012 20:50

Ahoj ↑ Skrblik:,
No pre taketo male cislo mozes najprv vypocitat priblizne druhu odmocninu a skusat systematicky delit tvoje cislo vsetkymy prvocislamy mensimy ako ta odmocnina. ( ak sa podari nejaky podiel bez zvysku, tak tvoje cislo nie je prvocislo; inac JE.. ak sa ziadne delenie nedalo cele cislo)
A vies dokazat preco funguje tato metoda?

Skrblik · 05. 01. 2012 20:55

Ano, skutečně to funguje. Asi plácnu blbost, ale... že by každé číslo a, které je dělitelem čísla b bylo také dělitelem druhé odmocniny b? Ale fakt nevim.

vanok · 05. 01. 2012 21:01

↑ Skrblik:,
Nie to skor preto ak pre cislo napriklad n mas rozklad n=m*k tak jedno z tych cisiel je mensie ako odmocnina z n a druhe vedcie ako odmocnina z n .

To preto : ak obe by boli mensie (vedcie) ako odmocnina tak aj ich sucin by bol mensi (vedci) ako cislo n

Skrblik · 05. 01. 2012 21:04

Ano, máš pravdu. Jsi borec! Díky za pomoc.
Určitě se zase někdy stavím - matika mi nejde.

Měj se! Ahoj.

Skrblik · 05. 01. 2012 21:47

Jo a ještě:
Nevíte někdo, jak nastavit kalkulačku CASIO fx-58ES, aby dělila se zbytkem?

Anonymystik

↑ Skrblik: Existují i tzv. pravděpodobnostní testy. Většina z nich nějakým způsobem využívá tzv. malou Fermatovu větu: je-li p prvočíslo a čísla "a" je nesoudlné s číslem p, pak $a^{p-1}$ dává zbytek 1 po dělení číslem p. Bohužel tato věta neplatí obráceně - tzn. neplatí, že pokud p je složené číslo, pak $a^{p-1}$ nedává zbytek 1 po dělení číslem p. Ten zbytek 1 je nutná, ale ne postačující podmínka pro prvočíselnost.

Takže: vezměš vhodné číslo a nesoudělné s p, vypočítáš $a^{p-1}$ a ověříš zbytek po dělení číslem p. Pokud $a^{p-1}$ je 1, tak se MŮŽE jednat o prvočíslo (ale NEMUSÍ). Tzn. vybereš víc různých čísel "a" a pro ně provedeš ten samý test. Pokud ti aspoň jeden z nich nevyjde, jedná se určitě o složené číslo. Pokud všechny vyjdou, tak se jasná ASI o prvočíslo (pravděpodobnost se zvyšuje s počtem provedených testů). Je však zajímavé, že vyjde-li ti, že p je složené číslo (a to víš určitě, nejen asi), tak vlastně ani neznáš jeho dělitele.

Problematický krok se ti asi bude jevit určování zbytku čísla $a^{p-1}$ po dělení číslem p, protože zpravidla p je hodně velké číslo. Existují na to vhodné metody, které vychází z teorie čísel (kongruence), které obvykle počítač zvládá relativně rychle (rozhodně řádově rychleji, než kdyby prostě jen hledal prvočíselné dělitele až do odmocniny z daného čísla), ale člověku trvají dlouho. Proto pro ruční ověřování prvočísel osobně doporučuji právě hledání prvočíselných dělitelů až po odmocninu z daného testu.

Jinak existují různé modifikace a vylepšení tohoto testu. Jedním z nich je tzv. Rabin-Millerův test a ten zrovna programuju u sebe na počítači. V podstatě jde o to, že se zesílí podmínka pro prvočíselnost (stále však ale není postačující), a tudíž se vyloučí více složených čísel, která by se v obyčejném Fermatově testu jevila jako pseudoprvočísla.

Matej1117

Mala fermatova veta:
cislo ktore chces overit, nech je X
"a" nech je lubovolne cele cislo ( najlepsie najmensie cele cize 2)
potom ak (a^X - a)/X je rovne celemu cislu, X je prvocislo. Ak (X^a - X)/a je rovne cislu s desatinym rozvojom, napr. 2,458... X nie je prvocislo.
Takto mozes overit akekolvek cislo, jedina nevyhoda je ze pri velkych prvocislach je to velmi neefektivne a zdlhave.
Napriklad ak by si chcel overit cislo 101 ci je prvocislo. Touto metodou by si najprv za "a" zvolil nejake cislo, najlepsie najmensie cize 2.
(2^101 - 2)/101 = (2535301200456458802993406410752 - 2)/101 = 25101992083727314881122835750 - toto je cele cislo, cize 101 je prvocislo.

Ale co ked budes musiet overit ci je 10000001 prvocislo?? To ti uz ani kalkulacka pri tejto metode nepomoze.. vtedy treba pouzit inu metodu.

Anonymystik

↑ Matej1117: Vezměme tedy např. číslo 101. To rozepíšeme jako $101 = 1*2^{6} + 1*2^{5}+ 0*2^{4}+ 0*2^{3}+ 1*2^{2}+ 0*2^{1}+ 1*2^{0}$ (v podstatě se jedná o převod do binární soustavy). Tohle můžeš pomocí Hornerova schéma napsat taky jako $101 = (((((((1)*2+1)*2+0)*2+0)*2+1)*2+0)*2+1)$ , a tedy $a^{101} = a^{(((((((1)*2+1)*2+0)*2+0)*2+1)*2+0)*2+1)}$ (*). To se zdá šílené, ale ve skutečnosti to taková hrůza není. Za chvíli uvidíš, proč.
---
Celý ten exponent si můžeš napsat ve tvaru "nejvnitřnější závorka * ten zbytek za závorkou". My si označíme nejvnitřnější závorku jako $z$ , a to, co zbývá za závorkou, jako $r$ . Celý výraz můžeš napsat jako $a^{rz} = (a^{z})^{r}$ . Jenže číslo $a^{z}$ spočítáš snadno. Označme výsledek jako b. Potom zřejmě $a^{rz} = b^{r}$ . Nyní využijeme následující tvrzení: pokud x, y dávají stejný zbytek po dělení číslem p, tak i čísla $x^{n}$ , $y^{n}$ dávají stejný zbytek. Tudíž: chceme-li zůstat v co nejmenších číslech, tak vypočítáme si zbytek po čísla b po dělení číslem p, označíme jej c. Určitě bude platit, že $c\le p-1$ (**). A protože čísla b, c dávají stejný zbytek po dělení číslem p, tak $b^{r}$ , $c^{r}$ jistě dávají stejný zbytek. Stačí ti tedy už jen určit, jaký zbytek dává číslo $c^{r}$ po dělení číslem p, což je stejný problém, jaký jsme řešili na začítku, až na to, že r má o jednu závorku méně než šílený exponent u původního problému (*).
---
Počet závorek je ale nejvýše $\log_2{p}$ , což ani pro opravdu velká p není závratně velké číslo. Navíc každý jednotlivý krok je pro počítač zvládnutelný, protože v podstatě v každém kroku počítá pouze dva výpočty:
(1) určuje zbytek čísla b po dělení číslem p
(2) určuje číslo $b^{z}$ , kde z je ale vzhledem ke struktuře Hornerova schémata vždy roven buď 2, nebo 3, zatímco p je podle (**) menší než p. Takže se umocňuje číslo menší než p na druhou nebo na třetí, což ani pro velká vstupní čísla p není neuskutečnitelné.
---
A tyto kroky se opakují tak dlouho, dokud už ti v aktuálním r nezbude žádná závorka. Takto se dají spočítat zbytky opravdu velkých čísel ve tvaru "něco na něco", kde to "druhé něco" je hodně velké číslo.

vanok · 06. 01. 2012 18:43

Ahoj↑ Anonymystik:,↑ Matej1117:,
Vase uvahy su zaujimave... ale asi nepatria na srednu skolu...
Mozte otvorit na tuto temu novu temu na urovni Vysoka Skola

Matematické Fórum

#1 05. 01. 2012 20:45

Jak zjistit, zda je číslo prvočíslo?

#2 05. 01. 2012 20:50

Re: Jak zjistit, zda je číslo prvočíslo?

#3 05. 01. 2012 20:55

Re: Jak zjistit, zda je číslo prvočíslo?

#4 05. 01. 2012 21:01

Re: Jak zjistit, zda je číslo prvočíslo?

#5 05. 01. 2012 21:04

Re: Jak zjistit, zda je číslo prvočíslo?

#6 05. 01. 2012 21:47

Re: Jak zjistit, zda je číslo prvočíslo?

#7 05. 01. 2012 23:28 — Editoval Anonymystik (05. 01. 2012 23:35)

Re: Jak zjistit, zda je číslo prvočíslo?

#8 05. 01. 2012 23:30 Příspěvek uživatele Anonymystik byl skryt uživatelem Anonymystik.

#9 06. 01. 2012 15:43 — Editoval Matej1117 (06. 01. 2012 15:45)

Re: Jak zjistit, zda je číslo prvočíslo?

#10 06. 01. 2012 17:34 — Editoval Anonymystik (06. 01. 2012 17:48)

Re: Jak zjistit, zda je číslo prvočíslo?

#11 06. 01. 2012 18:43

Re: Jak zjistit, zda je číslo prvočíslo?

Zápatí