Úvod
V tomto článku bude zverejnený efektívny algoritmus na testovanie extrémne veľkých čísiel (autor: Robopol). Algoritmus otestuje číslo a vyhodnotí, či sa jedná o zložené číslo alebo prvočíslo. Tento diel je zároveň update článku z minulosti - Program na prvočísla. Algoritmus je naprogramovaný v programovacom jazyku Python. Pre bližšie informácie o Pythone (inštalácia, spustenie..) navštívte stránku - Matematika v Pythone, resp. informácie sú dostupné online na internete.V algoritme sa využívajú aj vzťahy (Robopol theorem):
Verzie algoritmu, zdrojový kód
Obr. 1 Užívateľské prostredie programu
Verzia č.1:
download súboru v Pythone: prime_numbers.py
download súboru - Github: prime_numbers.py
spustiteľný ".exe" súbor: prime_number.exe
Popis: Algoritmus obsahuje klasické vyhľadávanie prvočísiel + špeciálny algoritmus na extrémne veľké čísla.
Spustenie kódu:
Pre spustenie konzolového programu je potrebné si nainštalovať Python. Následne po inštalácii spustíme interpretéra s názvom IDLE(..) , ktorý je nainštalovaný v ponuke štart. Otvoríme Python súbor(koncovka ". py"):
Obr.2 Otvorenie kódu v IDLE, zdroj: vlastný obrázok.
Následne spustíme kód v ponuke Run, Run module. Následne sa spustí kód kde zadávame čísla. Veľké čísla si môžete kopírovať a vkladať, viď. nižšie na príklade. Ukončenie programu je zadaním 0 a potvrdením cez enter.
Online spustenie programu:
Kód si môžete spustiť aj online na prehliadači napr. na stránke: https://www.onlinegdb.com/online_python_interpreter
Následne si skopírujte celý kód programu z textového súboru, viď. verzia vyššie. Potom už len spustíme program cez Run. Pozor však na veľkosť čísla, tento server ma limit a pri veľkých číslach vyhodí zlý výsledok.
Obr.3 Online spustenie programu, zdroj: vlastný obrázok.
Príklady extrémnych prvočísiel
Vyskúšame teraz ako rýchly je tento algoritmus na bežnom pc s troška lepšou grafickou kartou, priemerným procesom a 16 GB RAM:Pre zaujímavosť nech sa trocha zapotí si vyberieme Mersennové prvočísla. (https://sk.wikipedia.org/wiki/Mersennovo_prvo%C4%8D%C3%ADslo)
vyberieme si napr. číslo na 25. pozícií s 6533 ciframi. Najskôr však potrebujeme mať celý číselný tvar. Otvoríme si teda príkazový riadok cmd, napíšeme Python, čím spustíme Python v príkazovom riadku Windowsu. vypočítame hodnotu 2ˆ21701-1:
Obr.4 Výpočet 2 ˆ21701-1 v Pythone, zdroj: vlastný obrázok.
Následne si skopírujeme toto číslo do otvoreného programu pre zadanie čísiel.
Obr. 5 Výsledok v programe, zdroj: vlastný obrázok.
Algoritmus zhruba za 45 sec vyhodí výsledok, že ide o prvočíslo, resp. pseudoprvočíslo. To je veľmi dobrý výsledok v rýchlosti.
Pri skúšaní čísiel môžeme meniť parametre v programe, teda konštanty:
1. Môžeme meniť základ Fermatovej vety, premenná "a", napr. chceme posúdiť výsledok aj pre a=3,4,5,7..atď.
2. Môžeme meniť big_num, big_num1, čo sú konštanty pokiaľ ma klasický algoritmus hľadať deliteľov.
3. Môžeme meniť aj b_first, čo je počiatočná premenná v algoritme, no zmena neprinesie žiaden viditeľný rozdiel, preto je hodnota nižšia, nezadávajte viac ako 1000.