Obsah

• Na krok
• Metóda 1 zo 4: Skúste rozdeliť
• Metóda 2 zo 4: Použitie Fermatovej malej vety
• Metóda 3 zo 4: Použitie Miller-Rabinovho testu
• Metóda 4 zo 4: Použitie vety o čínskom zvyšku
• Tipy
• Nevyhnutnosť

Prvočísla sú čísla, ktoré sú deliteľné iba sami o sebe a nazývajú sa 1 - iné čísla zlúčenina čísla. Pokiaľ ide o testovanie, či je číslo prvočíslo, existuje niekoľko možností. Niektoré z týchto metód sú pomerne jednoduché, ale pre väčšie počty nie sú vôbec praktické. Ostatné často používané testy sú skutočne úplné algoritmy založené na jednom pravdepodobnosť ktorí niekedy mylne považujú číslo za prvočíslo. Pokračujte krokom 1 a naučte sa, ako sa otestovať, keď máte do činenia s prvočíslom.

Na krok

Metóda 1 zo 4: Skúste rozdeliť

Pokus o rozdelenie je zďaleka najjednoduchší spôsob, ako otestovať číslo. Pre malé počty je to zvyčajne tiež najrýchlejší spôsob. Test je založený na definícii prvočísla: číslo je prvočíslo, ak je deliteľné iba sebou a 1.

1. Predpokladajme n je číslo, ktoré chcete otestovať. Vydeľte číslo n všetkými možnými deliteľnými celými číslami. Pre väčšie čísla, ako je n = 101, je nesmierne nepraktické deliť ho možným celým číslom menším ako n. Našťastie existuje niekoľko trikov, ako znížiť počet testovaných faktorov.
2. Určite, či n dokonca. Všetky párne čísla sú úplne deliteľné číslom 2. Preto, ak je n párne, môžete to povedať n je zložené číslo (a teda nie prvočíslo). Ak chcete rýchlo zistiť, či je číslo párne, musíte venovať pozornosť iba poslednej číslici. Ak je posledná číslica 2, 4, 6, 8 alebo 0, potom je číslo párne a nie prvočíselné.
   • Jedinou výnimkou z tohto pravidla je samotné číslo 2, ktoré je preto, že je deliteľné samo sebou a číslom 1, tiež prvočíslo. 2 je jediný párny prime.
3. Časť n akýmkoľvek číslom od 2 do n-1. Pretože prvočíslo nemá žiadne iné faktory ako seba a 1, a pretože celočíselné faktory sú menšie ako ich súčin, kontrola deliteľnosti celého čísla menšia ako n a väčšia ako 2 určí, či je n prvočíslo. Začíname po 2, pretože párne čísla (násobky 2) nemôžu byť prvočíslami. Toto nie je ani zďaleka efektívny spôsob testovania, ako uvidíte ďalej.
   • Napríklad, ak by sme chceli touto metódou otestovať, či je 11 prvočíslo alebo nie, vydelíme 11 číslicami 3, 4, 5, 6, 7, 8, 9 a 10 a bez zvyšku hľadáme celočíselnú odpoveď. Pretože žiadne z týchto čísel sa nezmestí úplne do 11, môžeme povedať, že 11 je jedna je prime.
4. Ak chcete ušetriť čas, testujte iba do sqrt (n), zaokrúhlené nahor. Testovanie čísla n kontrolou všetkých čísel medzi 2 a n-1 môže rýchlo trvať veľa času. Napríklad, ak by sme chceli skontrolovať, či je touto metódou prvočíslo 103, museli by sme ho vydeliť 3, 4, 5, 6, 7 ... atď., A to až na 102! Našťastie nie je potrebné takto testovať. V praxi je potrebné testovať iba faktory medzi 2 a druhou odmocninou n. Ak druhá odmocnina čísla n nie je číslo, zaokrúhlite ho na najbližšie celé číslo a vyskúšajte toto číslo. Vysvetlenie nájdete nižšie:
   • Poďme preskúmať faktory 100. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2 a 100 × 1. Upozorňujeme, že po 10 × 10 sú faktory rovnaké ak to na 10 × 10, tak až potom otočené. Všeobecne môžeme faktory n väčšie ako sqrt (n) ignorovať, pretože sú iba pokračovaním faktorov menších ako sqrt (n).
   • Skúsme príklad. Ak n = 37, potom nemusíme testovať všetky čísla od 3 do 36, aby sme zistili, či je n prvočíslo. Namiesto toho sa stačí pozrieť na čísla medzi 2 a sqrt (37) (zaokrúhlené nahor).
     • sqrt (37) = 6,08 - zaokrúhlime to na 7.
     • 37 nie je úplne deliteľné 3, 4, 5, 6 a 7, takže môžeme s istotou tvrdiť, že je to jeden prvočíslo je.
5. Aby sme ušetrili ešte viac času, používame iba hlavné faktory. Je možné urobiť testovací proces delením ešte kratším tým, že sa nezahrnú tie faktory, ktoré nie sú prvočíslami. Podľa definície možno každé zložené číslo vyjadriť ako súčin dvoch alebo viacerých prvočísel. Takže delenie čísla n zloženým číslom je zbytočné - to sa rovná niekoľkonásobnému deleniu prvočíslami. Takže môžeme ďalej zúžiť zoznam možných faktorov iba na prvočísla menšie ako sqrt (n).
   • To znamená, že je možné preskočiť všetky párne faktory, ako aj faktory, ktoré sú násobkami prvočísel.
   • Skúsme napríklad určiť, či je 103 prvočíslo. Druhá odmocnina čísla 103 je 11 (zaokrúhlená nahor). Prvočísla medzi 2 a 11 sú 3, 5, 7 a 11. 4, 6, 8 a 10 sú párne a 9 je násobok 3, prvočíslo, takže ho môžeme preskočiť. Týmto sme znížili zoznam možných faktorov na iba 4 čísla!
     • 103 nie je úplne deliteľné 3, 5, 7 alebo 11, takže teraz vieme, že 103 je jeden prvočíslo je.

Metóda 2 zo 4: Použitie Fermatovej malej vety

V roku 1640 francúzsky matematik Pierre de Fermat prvýkrát navrhol vetu (teraz pomenovanú po ňom), ktorá môže byť veľmi užitočná pri určovaní, či je alebo nie je číslo prvočíslo. Technicky je cieľom Fermatovho testu overiť, či je číslo zložené a nie prvočíselné. Je to tak preto, lebo test dokáže s „absolútnou istotou“ preukázať, že číslo je zložené, ale iba „s pravdepodobnosťou“, že číslo je prvočíslo. Fermatova malá veta je užitočná v situáciách, keď je pokus o rozdelenie nepraktický a keď je k dispozícii zoznam čísel, ktoré sú výnimkou z vety.

1. Predpokladajme n číslo je na testovanie. Týmto testom určíte, či je dané číslo n prvočíslo. Ako je však uvedené vyššie, táto veta môže občas chybne charakterizovať niektorú zlúčeninu ako prvočíslo. Je dôležité vziať to do úvahy a skontrolovať svoju odpoveď, ktorá je vysvetlená nižšie.
2. Vyberte celé číslo a medzi 2 a n-1 (vrátane). Presné celé číslo, ktoré vyberiete, nie je dôležité. Pretože parametre pre zahrnutie 2 a n-1, môžete ich tiež použiť.
   • Príklad: Je 100 prvočísel alebo nie. Predpokladajme, že to vezmeme 3 ako testovacia hodnota - je to medzi 2 a n-1, takže to stačí.
3. vypočítať a (mod n). Vypracovanie tohto výrazu si vyžaduje určité znalosti matematického systému zvaného modulárna matematika. V modulárnej matematike sa čísla vrátia na nulu po dosiahnutí určitej hodnoty, známej tiež ako modul. Môžete to myslieť ako hodiny: nakoniec sa ručička hodín vráti na 1 hodinu po 12 hodine, nie na 13 hodín. Modul sa označuje ako (mod n). Takže v tomto kroku vypočítate a s modulom n.
   • Ďalšou metódou je výpočet a, potom ho vydelte n a zvyšok použite ako svoju odpoveď. Špecializované kalkulačky s funkciou modulu môžu byť veľmi užitočné pri delení veľkých čísel, pretože môžu okamžite vypočítať zvyšok rozdelenia.
   • Pomocou takejto kalkulačky v našom príklade vidíme, že 3/100 má zvyšok 1. Takže 3 (mod 100) je 1.
4. Ak to vypočítame ručne, použijeme exponent ako krátky formát. Ak nemáte kalkulačku s funkciou modulu, uľahčite postup pri určovaní zvyšku pomocou zápisu s exponentom. Pozri nižšie:
   • V našom príklade počítame 3 s modulom 100. 3 je veľmi, veľmi veľké číslo - 515 377 520 0 732 011 331 036 461 129 9765 621 272 702 107 5222 001 - také veľké, že je veľmi ťažké s ním pracovať. Namiesto použitia 48-cifernej odpovede pre 3 radšej ju napíšeme ako exponent, takže (((((((3)*3))))*3)). Pamätajte, že získanie exponenta exponenta má za následok jeho vynásobenie ((x) = x).
     • Teraz môžeme určiť zvyšok. Začnite riešením ((((((((3) * 3))))) * *) vo vnútornej množine zátvoriek a postupujte postupne tak, že každý krok vydelíte 100. Keď už nájdeme zvyšok, použijeme to skôr na ďalší krok ako na skutočnú odpoveď. Pozri nižšie:
       • (((((((((9) * 3)))) * *) - 9/100 nemá zvyšok, takže môžeme pokračovať.
       • (((((((27)))) * *) - 27/100 nemá zvyšok, takže môžeme ísť ďalej.
       • (((((729))) * 3)) - 729/100 = 7 R 29. Náš zvyšok je 29. Pokračujeme ďalším krokom, nie 729.
       • ((((29=841)) * 3)) - 841/100 = 8 R 41. Zvyšok 41 znovu použijeme v ďalšom kroku.
       • (((41 = 1681) * 3)) - 1681/100 = 16 R 81. Zvyšok 81 použijeme v ďalšom kroku.
       • ((81*3 = 243)) - 243/100 = 2 R 43. Zvyšok 43 použijeme v ďalšom kroku.
       • (43 = 1849) - 1849/100 = 18 R 49. Zvyšok 49 použijeme v ďalšom kroku.
       • 49 = 2401 - 2401/100 = 24 R 1. náš konečný zvyšok je 1. Inými slovami, 3 (mod 100) = 1. Upozorňujeme, že ide o rovnakú odpoveď, akú sme vypočítali v predchádzajúcom kroku!
5. Zistite, či a (mod n) = a (mod n). Ak nie, n je zlúčenina. Ak je to pravda, potom n pravdepodobne (ale nie som si istý) prvočíslo. Opakovanie testu s rôznymi hodnotami pre a môže výsledok spresniť, ale existuje zriedkavé zložené číslo, ktoré uspokojí Fermatovu vetu pre všetko hodnoty a. Nazývajú sa Carmichaelove čísla - najmenšie z týchto čísel je 561.
   • V našom príklade 3 (mod 100) = 1 a 3 (mod 100) = 3,1 ≠ 3, takže môžeme povedať, že 100 je zložené číslo.
6. Použite čísla Carmichael, aby ste si boli istí svojim výsledkom. Ak budete vedieť, ktoré čísla zodpovedajú sérii Carmichael, skôr ako budete pokračovať, ušetrí vám to veľa starostí s tým, či je alebo nie je číslo prvočíslo. Všeobecne sú Carmichaelove čísla súčinom jednotlivých prvočísel, kde pre všetky prvočísla platí, že ak p je deliteľ n, potom aj p-1 je deliteľ n-1. Online zoznam Carmichaelových čísel môže byť pomocou Fermatovej malej vety veľmi užitočný na určenie, či je číslo prvočíslo.
   
   

Metóda 3 zo 4: Použitie Miller-Rabinovho testu

Miller-Rabinov test funguje rovnako ako Fermatova malá veta, ale lepšie sa zaoberá neštandardnými číslami, ako sú Carmichaelove čísla.

1. Predpokladajme n je nepárne číslo, ktoré chceme otestovať na primárnosť. Rovnako ako vo vyššie uvedených metódach, n je premenná, ktorej chceme určiť primárnosť.
2. Tlak n-1 v tvare 2 × d na ktorom d je nepárne. Číslo n je prvočíslo, ak je nepárne. Takže n - 1 musí byť párne. Pretože n - 1 je párne, dá sa to napísať ako mocnina dvojnásobku nepárneho čísla. Takže 4 = 2 × 1; 80 = 2 × 5; a tak ďalej.
   • Predpokladajme, že chceme zistiť, či n = 321 je prvočíslo. 321 - 1 = 320, ktoré môžeme vyjadriť ako 2 × 5.
     • V tomto prípade je n = 321 vhodné číslo. Stanovenie n - 1 pre n = 371 môže vyžadovať veľkú hodnotu pre d, čo sťažuje celý proces v neskoršej fáze. 371 - 1 = 370 = 2 × 185
3. Vyberte ľubovoľné číslo a medzi 2 a n-1. Nezáleží na presnom počte, ktoré vyberiete - iba to, že musí byť menšie ako n a väčšie ako 1.
   • V našom príklade s n = 321 zvolíme a = 100.
4. vypočítať a (mod n). Ak a = 1 alebo -1 (mod n), potom prejde n Miller-Rabinov test a je pravdepodobne prvočíslo. Rovnako ako Fermatova malá veta, aj tento test nedokáže s absolútnou istotou určiť primitívnosť čísla, vyžaduje však ďalšie testy.
   • V našom príklade s n = 321, a (mod n) = 100 (mod 321). 100 = 10 000 000 000 (mod 321) = 313. Na nájdenie zvyšku 100/321 používame špeciálnu kalkulačku alebo stenografickú metódu s exponentom, ako je popísané vyššie.
     • Pretože sme nezískali 1 alebo -1, nemôžeme s istotou povedať, že n je prvočíslo. Je však potrebné urobiť ešte viac - čítajte ďalej.
5. Pretože výsledok nie je rovný 1 alebo -1, vypočítajte a, a, ... a tak ďalej, až ad. Vypočítajte zvýšený na mocninu d krát, až do 2. Ak sa ktorákoľvek z nich rovná 1 alebo -1 (mod n), potom prejde n testuje Miller-Rabin a je pravdepodobne prvoradý. Ak ste zistili, že testom vyhovuje n, skontrolujte svoju odpoveď (pozri krok nižšie). Ak n niektorý z týchto testov nevyhovie, je to jeden zložený číslo.
   • Pripomíname, že v našom príklade je hodnota a 100, hodnota s 6 a d 5. Pokračujeme v testovaní, ako je uvedené nižšie:
     • 100 = 1 × 10.
       • 1 × 10 (mod 321) = 64,64 ≠’ 1 alebo -1. Pokračujte pokojne.
     • 100 = 1 × 10.
       • 1 × 10 (mod 321) = 244,244 ≠ 1 alebo -1.
     • V tomto okamihu môžeme prestať. s - 1 = 6 - 1 = 5. Teraz sme dosiahli 4d = 2 a neexistujú žiadne sily 2-krát d pod 5d. Pretože žiadny z našich výpočtov neodpovedal na hodnotu 1 alebo -1, môžeme povedať, že n = 321 zložený číslo je.
6. Ak n vyhovie Miller-Rabinovmu testu, opakujte pre ďalšie hodnoty a. Ak ste zistili, že hodnota n môže byť prvočíselná, skúste znova s ​​inou náhodnou hodnotou pre a, aby ste potvrdili výsledok testu. Ak n je skutočne prvočíslo, bude to platiť pre každú hodnotu a. Ak n je zložené číslo, zlyhá pre tri štvrtiny hodnôt a. To vám dáva väčšiu istotu ako Fermatova malá veta, kde je isté zložené čísla (čísla Carmichael) vyhovejú testu na akúkoľvek hodnotu a.

Metóda 4 zo 4: Použitie vety o čínskom zvyšku

1. Vyberte dve čísla. Jedno z čísel nie je prvočíslo a druhé je číslo, ktoré sa testuje na primárnosť.
   • "Číslo testu1" = 35
   • Číslo testu2 = 97
2. Vyberte dva dátové body väčšie ako nula a menšie ako TestNumber1 a TestNumber2. Nemôžu sa navzájom rovnať.
   • Dáta1 = 1
   • Dáta2 = 2
3. Vypočítajte MMI (matematická multiplikatívna inverzná hodnota) pre číslo testu 1 a číslo testu 2
   • Vypočítajte MMI
     • MMI1 = číslo testu2 ^ -1 číslo testu testu1
     • MMI2 = Číslo testu1 ^ -1 Číslo testu mod2
   • Iba pre prvočísla (výsledok bude pre prvočísla, ale to nie je MMI):
     • MMI1 = (TestNumber2 ^ (TestNumber1-2))% TestNumber1
     • MMI2 = (TestNumber1 ^ (TestNumber-2))% TestNumber2
   • Takže:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. Vytvorte binárnu tabuľku pre každé MMI až do hodnoty Log2 modulu
   • Pre MMI1
     • F (1) = počet testov 2% počet testov 1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% číslo testu 1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% číslo testu 1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% číslo testu 1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% číslo testu 1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% číslo testu 1 = 1 * 1% 35 = 1
   • Vypočítajte binárny logaritmus TestNumber1 - 2
     • 35 -2 = 33 (10001) základ 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 Mod 35
     • MMI1 = 27
   • Pre MMI2
     • F (1) = počet testov 1% počet testov 2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% číslo testu2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% číslo testu2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% číslo testu2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% číslo testu2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% číslo testu2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% číslo testu2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% číslo testu 2 = 35 * 35 mod 97 = 61
   • Vypočítajte binárny logaritmus TestNumber2 - 2
     • 97 - 2 = 95 = (1011111) základňa 2
     • MMI2 = (((((((F (64) * F (16)% 97) * F (8)% 97) * F (4)% 97) * F (2)% 97) * F) (1)% 97)
     • MMI2 = (((((((35 * 35)% 97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)
     • MMI2 = 61
5. Vypočítať (Data1 * TestNumber2 * MMI1 + Data2 * TestNumber1 * MMI2)% (TestNumber1 * TestNumber)
   • Odpoveď = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Odpoveď = (2619 + 4270)% 3395
   • Odpoveď = 99
6. Skontrolujte, či „TestNumber1“ nie je prime1
   • Vypočítajte (odpoveď - údaje1)% čísla testu1
   • 99 -1 % 35 = 28
   • Pretože 28 je väčšie ako 0, 35 nie je prvočíslo
7. Skontrolujte, či je TestNumber2 prvočíslo
   • Vypočítajte (odpoveď - údaje2)% čísla testu2
   • 99 - 2 % 97 = 0
   • Pretože 0 sa rovná 0, 97 je potenciálne prvočíslo
8. Zopakujte kroky 1 až 7 ešte najmenej dvakrát.
   • Ak sa krok 7 rovná 0:
     • Ak nie je TestNumber1 prvočíslo, použite iné „TestNumber1“.
     • Použite iné TestNumber1, kde je TestNumber1 skutočne prvočíslo. V tomto prípade sú kroky 6 a 7 rovné 0.
     • Pre dáta1 a dáta2 použite rôzne dátové body.
   • Ak je krok 7 vždy rovný 0, potom je pravdepodobnosť, že číslo 2 je prvočíslo, veľmi vysoká.
   • Je známe, že kroky 1 až 7 sú nesprávne v určitých prípadoch, keď prvé číslo nie je prvočíslo a druhé je prvočíselným faktorom neimpríselného čísla „Testovacie číslo1“. Funguje to vo všetkých scenároch, keď sú obidve čísla prvočíselné.
   • Kroky 1 až 7 sa opakujú preto, že existuje niekoľko scenárov, keď aj keď TestNumber1 nie je prime a TestNumber2 nie je prime, každé číslo z kroku 7 je stále nulové. Tieto stavy sú zriedkavé. Ak zmeníte TestNumber1 na iné než prvočíslo, pokiaľ TestNumber2 nebude prvočíslo, nebude sa v kroku 7 rovnať nule. S výnimkou prípadu, keď „TestNumber1“ je faktorom TestNumber2, budú prvočísla vždy nula. krok 7.

Tipy

• 168 prvočísiel do 1000 je: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997
• Ak je pokus o rozdelenie pomalší ako pri sofistikovanejších metódach, je to stále efektívne pri menších počtoch. Aj pri testovaní väčších čísel nie je nezvyčajné najskôr skontrolovať malé čísla, až potom prejsť na pokročilejšie metódy.

Nevyhnutnosť

• Papier, pero, ceruzka a / alebo kalkulačka na vypracovanie