Ú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):
![Screenshot - 1_ 4jpg](https://files.vlastnawebstranka.websupport.sk/f8/93/f8936043-54c8-42c5-acfc-7bab6476d3a9.jpg)
Verzie algoritmu, zdrojový kód
![Screenshot - 17_ 7jpg](http://files.vlastnawebstranka.websupport.sk/3a/0d/3a0d9c0d-c080-447d-8d30-0dbb19f5ff54.jpg)
Obr. 1 Užívateľské prostredie programu
Verzia č.1:
download súboru v Pythone: prime_numbers.py(staršia verzia)
download súboru - Github: prime_test_GUI.py (novšia verzia s GUI)
spustiteľný ".exe" súbor: setup_prime_number.exe (staršia verzia)
spustiteľný ".exe" súbor: setup_prime_numbers_GUI_2024.rar (novšia verzia s GUI)
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"):
![otvorenie_prime_numbersjpg](https://files.vlastnawebstranka.websupport.sk/33/56/3356cd81-a26a-47ab-be0c-0a47a7aa20c4.jpg)
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.
![online_interprete_pythonjpg](https://files.vlastnawebstranka.websupport.sk/e9/af/e9af0721-7e81-4f47-9660-e01357a77ce8.jpg)
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:
![mesrenn_prime25jpg](https://files.vlastnawebstranka.websupport.sk/45/63/45634be9-2427-473c-8fb9-b8684a1c2ae7.jpg)
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.
![Skuska_2jpg](https://files.vlastnawebstranka.websupport.sk/94/a2/94a2dc82-e5dd-43ff-b838-3b1f55cead94.jpg)
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.