Projekt distribuovaných výpočtov objavil nové najväčšie prvočíslo
Diskusia k článku: Projekt distribuovaných výpočtov objavil nové najväčšie prvočíslo
Prispievajte do diskusií ako
prihlásený užívateľ.
Komentár, na ktorý odpovedáte:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Re: Prvočísla
Od: 1337
|
Pridané:
2016-01-20 20:52:41
Vychadza to z principu, ze kazde zlozene cislo (tj. cislo, ktore nie je prvocislo) sa da rozlozit na sucin prvocisel. Napr. 48=2*2*2*2*3
Prvocisla sa nedaju napisat ako sucin prvocisel (na tychto principoch je tiez zalozena kryptografia).
Ked sa snazis zistit, ci nejake cislo je prvocislo, tak ho zacnes delit cislami od 2, tak ako to mas v tvojom algoritme. No ked v prvom kroku zistis, ze cislo nie je delitelne 2, tak nebude delitelne ani nasobkami 2, teda 4, 6, 8, atd. Vsetky nasobky 2 tak mozes vynechat z tvojich "i". Takisto ked uz raz preskumas trojku, nemusis sa zabyvat nasobkami 3. Vo vysledku vzdy staci preskumat ci je dane cislo delitelne prvocislami a na zlozene cisla sa mozes vykaslat. Staci teda skumat i = {2,3,5,7,11,...}. Samozrejme pri pouziti tejto "optimalizacie" musis poznat vsetky prvocisla do sqrt(cislo).
|