Matematické Fórum

↑ Matej1117:
Ne.

ja neviem po anglicky.. nemohol by si mi aspon cast s toho prelozit?
zdenek a to vazne neexistuje ziadny vzorec na to? Nieco musi byt nie? Ved dnesna matematika je uz dost vyspela urcite nieco je len otom asi nevies.

↑ Matej1117: Sprav si program (predpoklad, že vieš programovať). Alebo skús nájsť na internete aplikáciu, ktorá to bude robiť.

Alebo použi algoritmus, s ktorým sa určite dopracuješ k správnemu riešeniu:

1) Nech n je číslo o ktorom chceš rozhodnúť, či je prvočíslo.
2) sprav
3) všetkými prirodzenými číslami od do (vrátane n) skúšaj vydeliť  číslo n
4) ak nájdeš deliteľa, tak to nie je prvočíslo.

Prečo akurát druhá odmocnina? Za druhou odmocninou sa už nenachádza deliteľ, ktorý by nebol násobkom deliteľa pred druhou odmocninou. Rozmysli si prečo sám.

Postup môžeš samozrejme urýchliť. Ak číslo nie je párne, tak určite nebude deliteľné násobkami dvojky atď.

Časová zložitosť tohoto postupu je , najviac vykonáš zhruba porovnaní a to práve vtedy, keď je n prvočíslo. Nie je to žiadna sláva ale lepšie ako nič.

A ešte ... po spravení druhej odmocniny zanedbaj desatinnú časť.

↑ pizet: Jen malé doplnění k bodu 3, jak program (trochu) urychlit. Stačí zkoušet jen prvočísla v dané množině a ne všechna celá čísla (například na dělitele 9 bychom narazili již při zkoušení trojky).
Pakliže v programu nechceme mít nějakou velkou databázi prvočísel (a generovaly by se pomalu), tak můžeme udělat jen jakýsi kompromis mezi oběma metodami: Ten spočívá v tom, že budeme zkoušet jenom lichá čísla a dvojku vyzkoušíme zvlášť.
Například testování 47ky na prvočíselnost (zkoušíme všechna celá čísla):
2, 3, 4, 5, 6
A při testování jen lichými čísly a dvojkou:
2, 3, 5

Tento postup by mohl být až přibližně dvakrát rychlejší. Asymptotickou časovou složitost to ale nijak nevylepší - zůstane


Edit: ta časová složitost ukazuje, jak rychlý bude program v závislosti na velikosti vstupu. V tomto případě: pokud se vstup (velikost čísla na prvočíselný test) zvýší 2x, tak se potřebná doba zvětší jen -krát.

Edit 2: aha, pizet už to doplnil do svého příspěvku

↑ TomDlask: No áno :). Tým urýchlením som myslel to, čo ty, že ak pri vypisovaní narazí trebárs na fakt, že číslo nie je deliteľné dvomi, tak už nemusí skúšať násobky dvojky a keď tromi, tak to isté atď.

Riešiš KSP? Ak áno môžem vedieť tvoje meno? :)

↑ Matej1117: Možno by ťa ešte zaujímalo toto http://sk.wikipedia.org/wiki/Eratostenovo_sito ... je to síce trocha iné ale tiež zaujímavý algoritmus súvisiaci s prvočíslami :)

Áno pre veľké n to môže trvať dlho. :) Však si to skús spraviť. Tebe to bude iste trvať aj pre relatívne malé n celkom dlho :).

↑ Matej1117: To bola otáka na TomDlaska.

↑ Matej1117: Erastostenovo síto je způsob získávání prvočísel, ta metoda, která zde byla uvedena, je na otestování čísla zda-li je (nebo není) prvočíslem. Technika je podobná, protože jde o stejnou vlastnost - prvočíselnost.

↑ pizet: KSP bohužel neřeším, zato se letos pokouším o MO-P