Tjek om et tal er primtal

Primtal er tal, der kun er delelige med sig selv og kaldes 1 – andre tal sammensatte tal. Når det kommer til at teste, om et tal er primtal, er der flere muligheder. Nogle af disse metoder er relativt enkle, men absolut ikke praktiske for større antal. Andre test, der ofte bruges, er faktisk komplette algoritmer baseret på en sandsynlighed som nogle gange fejlagtigt klassificerer et tal som primtal. Læs videre på trin 1 for at lære, hvordan du tester dig selv, om du har med et primtal at gøre.

Trin

Metode 1 af 4: Prøv ved at dividere

At prøve ved at dividere er langt den nemmeste måde at teste et tal på. For små tal er det normalt også den hurtigste måde. Testen er baseret på definitionen af ​​et primtal: et tal er primtal, hvis det kun er deleligt med sig selv og 1.

Billede med titlen Tjek, om et tal er prime Trin 1
1. Par n er det nummer, du vil teste. Divider tallet n med alle mulige delelige heltal. For større tal, såsom n=101, er det ekstremt upraktisk at dividere med alle mulige heltal mindre end n. Heldigvis er der flere tricks til at reducere antallet af faktorer, der skal testes.
Billede med titlen Tjek, om et tal er prime Trin 2
2. Beslutte hvorvidt n endda er. Alle lige tal er fuldt delelige med 2. Derfor, hvis n er lige, kan du sige det n er et sammensat tal (og derfor ikke et primtal). For hurtigt at afgøre, om et tal er lige, skal du kun være opmærksom på det sidste ciffer. Hvis det sidste ciffer er 2, 4, 6, 8 eller 0, er tallet lige og ikke primetal.
  • Den eneste undtagelse fra denne regel er selve tallet 2, som, fordi det er deleligt med sig selv og 1, også er primtal. 2 er det eneste lige primtal.
  • Billede med titlen Tjek, om et tal er prime Trin 3
    3. En del n med et hvilket som helst tal mellem 2 og n-1. Da et primtal ikke har andre faktorer end sig selv og 1, og fordi faktorer af heltal er mindre end deres produkt, vil kontrol af deleligheden af ​​et heltal mindre end n og større end 2 afgøre, om n er primtal. Vi starter efter 2, fordi lige tal (multipler af 2) ikke kan være primtal. Dette er langt fra en effektiv måde at teste på, som du vil se nedenfor.
  • Hvis vi for eksempel ville bruge denne metode til at teste, om 11 er primtal eller ej, skulle vi dividere 11 med 3, 4, 5, 6, 7, 8, 9 og 10, hver gang vi leder efter et heltalsvar uden rest. Da ingen af ​​disse tal passer helt ind i 11, kan vi sige, at 11 er en prime er.
  • Billede med titlen Tjek, om et tal er prime Trin 4
    4. For at spare tid test kun op til sqrt(n), rundet op. At teste et tal n ved at tjekke alle tal mellem 2 og n-1 kan hurtigt blive meget tidskrævende. For eksempel, hvis vi ville kontrollere, om 103 er primtal ved hjælp af denne metode, skulle vi dividere med 3, 4, 5, 6, 7 ... etc., helt til 102! Heldigvis er det ikke nødvendigt at teste sådan. I praksis er det kun nødvendigt at teste med faktorerne mellem 2 og kvadratroden af ​​n. Hvis kvadratroden af ​​n ikke er et tal, afrund det til nærmeste heltal og test til dette tal. Se nedenfor for en forklaring:
  • Lad os undersøge faktorerne på 100. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2 og 100 × 1. Bemærk, at efter 10 × 10 er faktorerne de samme som for 10 × 10, kun omvendt. Generelt kan vi ignorere faktorerne på n større end sqrt(n), fordi de simpelthen er en fortsættelse af faktorer mindre end sqrt(n).
  • Lad os prøve et eksempel. Hvis n = 37, behøver vi ikke at teste alle tal fra 3 til 36 for at afgøre, om n er primtal. I stedet skal vi kun se på tallene mellem 2 og sqrt(37) (rundet op).
  • sqrt(37) = 6.08 – vi runder dette op til 7.
  • 37 er ikke fuldt deleligt med 3, 4, 5, 6 og 7, så vi kan med sikkerhed sige, at det er en primtal er.
  • Billede med titlen Tjek, om et tal er prime Trin 5
    5. For at spare endnu mere tid bruger vi kun prime factors. Det er muligt at gøre processen med at teste ved division endnu kortere ved ikke at medtage de faktorer, der ikke er primtal. Per definition kan ethvert sammensat tal udtrykkes som produktet af to eller flere primtal. Så det er unødvendigt at dividere tallet n med et sammensat tal - det svarer til at dividere med primtal flere gange. Så vi kan yderligere indsnævre listen over mulige faktorer til kun primtal mindre end sqrt(n).
  • Det betyder, at alle lige faktorer, såvel som dem, der er multipla af primtal, kan springes over.
  • Lad os for eksempel prøve at bestemme, om 103 er prime eller ej. Kvadratroden af ​​103 er 11 (rundet op). Primtallene mellem 2 og 11 er 3, 5, 7 og 11. 4, 6, 8 og 10 er lige, og 9 er et multiplum af 3, et primtal, så vi kan springe denne over. Ved at gøre dette reducerede vi vores liste over mulige faktorer til kun 4 numre!
  • 103 er ikke fuldt deleligt med 3, 5, 7 eller 11, så vi ved nu, at 103 er en primtal er.
  • Metode 2 af 4: Brug af Fermat .s lille teorem

    I 1640 fremsatte den franske matematiker Pierre de Fermat først en sætning (som nu er opkaldt efter ham), som kan være meget nyttig til at afgøre, om et tal er primtal eller ej. Teknisk set er Fermats test beregnet til at kontrollere, om et tal er sammensat, snarere end primtal. Dette skyldes, at testen med "absolut sikkerhed" kan vise, at et tal er sammensat, men kun en "sandsynlighed" om et tal er primtal. Fermats lille sætning er nyttig i situationer, hvor det ikke er praktisk at forsøge at dividere med, og når en liste over tal er tilgængelig, som er undtagelser fra sætningen.

    Billede med titlen Tjek, om et tal er prime Trin 6
    1. Formode n nummeret er til test. Du bruger denne test til at bestemme, om et givet tal n er primtal. Men som nævnt ovenfor kan denne sætning lejlighedsvis fejlagtigt karakterisere visse sammensætninger som primtal. Det er vigtigt at tage højde for dette og tjekke dit svar, som vil blive forklaret senere.
    Billede med titlen Tjek, om et tal er prime Trin 7
    2. Vælg et heltal -en mellem 2 og n-1 (inklusive). Det nøjagtige heltal, du vælger, er ikke vigtigt. Da parametrene for a er inklusive 2 og n-1, kan du også bruge disse.
  • Et eksempel: Er 100 et primtal eller ej?. Antag, at vi tager 3 som testværdi - dette er mellem 2 og n-1, så det er tilstrækkeligt.
  • Billede med titlen Tjek, om et tal er prime Trin 8
    3. Beregn -en (mod n). Udarbejdelse af dette udtryk kræver en vis viden om et matematisk system kaldet modulær matematik. I modulær matematik vender tal tilbage til nul, når de når en bestemt værdi, kendt som modul. Du kan tænke på dette som et ur: til sidst vil urviseren skyde tilbage til klokken 1 efter klokken 12, ikke til klokken 1. Modulet er noteret som (mod n). Så på dette trin beregner du med et modul på n.
  • En anden metode er at beregne a, og derefter dividere med n, og derefter bruge resten som dit svar. Specialiserede lommeregnere med en modulfunktion kan være meget nyttige, når man dividerer store tal, fordi de direkte kan beregne resten af ​​en division.
  • Ved at bruge sådan en lommeregner i vores eksempel kan vi se, at 3/100 har en rest på 1. Så 3 (mod 100) er 1.
  • Billede med titlen Tjek, om et tal er prime Trin 9
    4. Hvis vi beregner dette i hånden, bruger vi eksponenten som kort notation. Hvis du ikke har en lommeregner med en modulfunktion, skal du bruge eksponentiel notation for at gøre proceduren med at bestemme resten lettere. Se nedenunder:
  • I vores eksempel beregner vi 3 med et modul på 100. 3 er et meget, meget stort tal - 515,377,520,732,011,331,036,461,129,765,621,272,702,107,522,001 - så stort, at det bliver meget svært at arbejde med. I stedet for at bruge det 48-cifrede svar til 3, må vi hellere skrive det som en eksponent, så (((((((3)*3))))*3)). Husk at at tage eksponenten af ​​en eksponent giver effekten af ​​at gange eksponenterne ((x) = x).
  • Nu kan vi bestemme resten. Begynd at løse for (((((((3)*3))))*3)) ved det inderste sæt af parenteser, og arbejd dig ud, og divider hvert trin med 100. Når vi har fundet resten, bruger vi det til næste trin i stedet for som det egentlige svar. Se nedenunder:
  • ((((((9)*3))))*3)) - 9/100 har ingen rest, så vi kan fortsætte.
  • ((((((27))))*3)) - 27/100 har ingen rest, så vi kan fortsætte.
  • ((((((729)))*3)) - 729/100 = 7 R 29. Vores resterende er 29. Vi går videre til næste trin, ikke 729.
  • ((((29=841))*3)) - 841/100 = 8 R 41. Vi bruger vores resterende 41 igen i næste trin.
  • (((41 = 1681)*3)) - 1681/100 = 16 R 81. Vi bruger vores resterende 81 i næste trin.
  • ((81*3 = 243)) - 243/100 = 2 R 43. Vi bruger vores resterende 43 i næste trin.
  • (43 = 1849) - 1849/100 = 18 R 49. Vi bruger vores resterende 49 i næste trin.
  • 49 = 2401 - 2401/100 = 24 R 1. vores sidste rest er 1. Med andre ord, 3 (mod 100) = 1. Bemærk, at dette er det samme svar, som vi beregnede i det foregående trin!
  • Billede med titlen Tjek, om et tal er prime Trin 10
    5. Tjek evt -en (mod n) = -en (mod n). Hvis ikke, så er n sammensat. Hvis sandt, så er n sandsynligvis (men ikke sikker) et primtal. Gentagelse af testen med forskellige værdier for a kan gøre resultatet mere sikkert, men der er sjældne sammensatte tal, der opfylder Fermats sætning for alle værdier af en. Disse kaldes Carmichael-tallene - det mindste af disse tal er 561.
  • I vores eksempel er 3 (mod 100) = 1 og 3 (mod 100) = 3. 1 ≠ 3, så vi kan sige, at 100 er et sammensat tal.
  • 6. Brug Carmichael-tallene for at være sikker på dit resultat. At vide, hvilke tal der opfylder Carmichael-sekvensen, før du fortsætter, kan spare dig for en masse hovedpine om, hvorvidt et tal er primtal eller ej. Generelt er Carmichael-tal produktet af individuelle primtal, hvor det for alle primtal gælder, at hvis p er en divisor af n, så er p-1 også en divisor af n-1. Onlinelisten over Carmichael-tal kan være meget nyttig til at bestemme, om et tal er primtal ved hjælp af Fermats lille sætning.

    Metode 3 af 4: Brug af Miller-Rabin-testen

    Miller-Rabin-testen fungerer på samme måde som Fermats lille teorem, men behandler unormale tal som Carmichael-tal på en bedre måde.

    Billede med titlen Tjek, om et tal er prime Trin 12
    1. Par n er et ulige tal, som vi ønsker at teste for primalitet. Som i metoderne angivet ovenfor, er n den variabel, vi ønsker at bestemme primaliteten af.
    Billede med titlen Tjek, om et tal er prime Trin 13
    2. Travl n-1 rabat i form 2 × d hvorved d er mærkeligt. Tallet n er primtal, hvis det er ulige. Så n - 1 skal være lige. Da n - 1 er lige, kan det skrives som en potens af 2 gange et ulige tal . Så,4 = 2 × 1; 80 = 2 x 5; og så videre.
  • Antag, at vi ønsker at bestemme, om n = 321 er et primtal. 321 - 1 = 320, som vi kan udtrykke som 2×5.
  • I dette tilfælde er n = 321 et passende tal. Bestemmelse af n – 1 for n = 371 kan kræve en stor værdi for d, hvilket gør hele processen vanskeligere på et senere tidspunkt. 371 - 1 = 370 = 2 × 185
  • Billede med titlen Tjek, om et tal er prime Trin 14
    3. Vælg et hvilket som helst nummer -en mellem 2 og n-1. Det nøjagtige tal, du vælger, er ligegyldigt - bare at det skal være mindre end n og større end 1.
  • I vores eksempel med n = 321 vælger vi a = 100.
  • Billede med titlen Tjek, om et tal er prime Trin 15
    4. Beregn -en (mod n). hvis -en = 1 eller -1 (mod n), så modstårn Miller-Rabin-testen og er sandsynligvis et primtal. Som med Fermats lille sætning kan denne test ikke bestemme et tals primalitet med absolut sikkerhed, men har brug for yderligere test for at gøre det.
  • I vores eksempel med n = 321, a (mod n) = 100 (mod 321). 100 = 10.000.000.000 (mod 321) = 313. Vi bruger en speciel lommeregner eller stenografimetoden med en eksponent som beskrevet tidligere til at finde resten af ​​100/321.
  • Da vi ikke fik 1 eller -1, kan vi ikke med sikkerhed sige, at n er primtal. Men der er mere, vi skal gøre – læs videre.
  • Billede med titlen Tjek, om et tal er prime Trin 16
    5. Da resultatet ikke er lig med 1 eller -1, beregn-en, -en,... og så videre, op til -end. Beregn a i magten af ​​d gange, op til 2. Hvis en af ​​disse er lig med 1 eller -1 (mod n), så modstår n Miller-Rabin-testen og er sandsynligvis prime. Når du har fastslået, at n består testen, så tjek dit svar (se trin nedenfor). Hvis n ikke består nogen af ​​disse prøver, så er det en sammensat nummer.
  • Som en påmindelse, i vores eksempel er værdien af ​​a lig med 100, værdien af ​​s er 6 og af d5. Vi fortsætter med testning som angivet nedenfor:
  • 100 = 1×10.
  • 1×10 (mod 321) = 64. 64 ` 1 eller -1. Hold dig rolig.
  • 100 = 1×10.
  • 1×10 (mod 321) = 244. 244 1 eller -1.
  • På dette tidspunkt kan vi stoppe. s - 1 = 6 - 1 = 5. Vi er nu nået til 4d = 2, og der er ingen potenser på 2 gange d under 5d. Da ingen af ​​vores beregninger gav et 1 eller -1 som svar, kan vi sige, at n = 321 a sammensat nummer er.
  • Billede med titlen Tjek, om et tal er prime Trin 17
    6. hvis n opfylder Miller-Rabin-testen, og gentag derefter for de andre værdier af -en. Hvis du har fundet ud af, at værdien af ​​n godt kan være prime, prøv igen med en anden tilfældig værdi for a for at bekræfte resultatet af testen. Hvis n faktisk er primtal, vil dette gælde for enhver værdi af a. Hvis n er et sammensat tal, vil det fejle i tre fjerdedele af værdierne af a. Dette giver dig mere sikkerhed end med Fermats lille sætning, hvor visse sammensatte tal (Carmichael-tallene) består testen for hver værdi af en.

    Metode 4 af 4: Brug af den kinesiske restsætning

    Billede med titlen Tjek, om et tal er prime Trin 18
    1. Vælg to tal. Et af tallene er ikke primtal, og det andet er det tal, der testes for primalitet.
    • "test nummer 1" = 35
    • Test nummer2 = 97
    Billede med titlen Tjek, om et tal er prime Trin 19
    2. Vælg to datapunkter større end nul og mindre end TestNumber1, henholdsvis TestNumber2. De kan ikke være ens.
  • Data1 = 1
  • Data2 = 2
  • Billede med titlen Tjek, om et tal er prime Trin 20
    3. Beregn MMI (Mathematical Multiplicative Inverse) for TestNumber1 og TestNumber2
  • Beregn MMI
  • MMI1 = Test Number2 ^ -1 Mod Test Number1
  • MMI2 = Test Number1 ^ -1 Mod Test Number2
  • Kun for primtal (der vil være et resultat for ikke-primtal, men det er ikke MMI):
  • MMI1 = (TestNumber2 ^ (TestNumber1-2)) %TestNumber1
  • MMI2 = (Test Number1 ^ (Test Number-2)) % Test Number2
  • Så:
  • MMI1 = (97^33) %35
  • MMI2 = (35^95) %97
  • Billede med titlen Tjek, om et tal er prime Trin 21
    4. Opret en binær tabel for hver MMI op til Log2 af modulet
  • Til MMI1
  • F(1) = Test Number2 % Test Number1 = 97 % 35 = 27
  • F(2) = F(1) * F(1) % Testnummer1 = 27 * 27 % 35 = 29
  • F(4) = F(2) * F(2) % Testnummer1 = 29 * 29 % 35 = 1
  • F(8) = F(4) * F(4) % Testnummer1 = 1 * 1 % 35 = 1
  • F(16) =F(8) * F(8) % Testnummer1 = 1 * 1 % 35 = 1
  • F(32) = F(16) * F(16) % Testnummer1 = 1 * 1 % 35 = 1
  • Beregn den binære logaritme af Testnummer1 - 2
  • 35 -2 = 33 (10001) base 2
  • MMI1 = F(33) = F(32) * F(1) mod 35
  • MMI1 = F(33) = 1 * 27 Mod 35
  • MMI1 = 27
  • Til MMI2
  • F(1) = Test Number1 % Test Number2 = 35 % 97 = 35
  • F(2) = F(1) * F(1) % Test Number2 = 35 * 35 mod 97 = 61
  • F(4) = F(2) * F(2) % Test Number2 = 61 * 61 mod 97 = 35
  • F(8)= F(4) * F(4) % Test Number2 = 35 * 35 mod 97 = 61
  • F(16) = F(8) * F(8) % Test Number2 = 61 * 61 mod 97 = 35
  • F(32)= F(16) * F(16) % Test Number2 = 35 * 35 mod 97 = 61
  • F(64)= F(32) * F(32) % Test Number2 = 61 * 61 mod 97 = 35
  • F(128) = F(64) * F(64) % Test Number2 = 35 * 35 mod 97 = 61
  • Beregn den binære logaritme af TestNumber2 - 2
  • 97 - 2 = 95 = (1011111) base 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
  • Billede med titlen Tjek, om et tal er prime Trin 22
    5. Beregn (Data1 * TestNumber2 * MMI1 + Data2 * TestNumber1 * MMI2) % (TestNumber1 * TestNumber)
  • Svar = (1 * 97 * 27 + 2 * 35 * 61) % (97 * 35)
  • Svar = (2619 + 4270) % 3395
  • Svar = 99
  • Billede med titlen Tjek, om et tal er prime Trin 23
    6. Tjek evt "test nummer 1" er ikke prime 1
  • Beregn (Svar - Data1) % Test Antal1
  • 99 -1 % 35 = 28
  • Da 28 er større end 0, er 35 ikke primtal
  • Billede med titlen Tjek, om et tal er prime Trin 24
    7. Tjek, om TestNumber2 er et primtal
  • Beregn (Svar - Data2) % Test Antal2
  • 99 - 2 % 97 = 0
  • Da 0 er lig med 0, er 97 et potentielt primtal
  • Billede med titlen Tjek, om et tal er prime Trin 25
    8. Gentag trin 1 til 7 mindst to gange mere.
  • Hvis trin 7 er lig med 0:
  • Brug en anden "test nummer 1" hvis TestNumber1 ikke er prime.
  • Brug et andet TestNumber1, hvor et TestNumber1 faktisk er et primtal.I dette tilfælde er trin 6 og 7 lig med 0.
  • Brug forskellige datapunkter til data1 og data2.
  • Hvis trin 7 altid er lig med 0, så er sandsynligheden for, at tal2 er primtal, meget stor.
  • Trin 1 til 7 vides at være forkerte i visse tilfælde, hvor det første tal ikke er primtal, og det andet er en primtal af det ikke-primtal "test nummer 1".Det virker i alle scenarier, hvor begge tal er primtal.
  • Grunden til, at trin 1 til 7 gentages, er, at der er nogle få scenarier, hvor, selvom TestNumber1 ikke er primtal, og TestNumber2 ikke er primtal, er begge tal fra trin 7 stadig nul.Disse tilstande er sjældne.Ved at ændre TestNumber1 til et andet ikke-primtal, hvis TestNumber2 ikke er primtal, vil TestNumber2 ikke længere være lig med nul i trin 7. Med undtagelse af det tilfælde, hvor "test nummer 1" er en faktor af TestNumber2, vil primtal altid være nul i trin 7.
  • Tips

    • De 168 primtal under 1000 er: 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. , 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311. , 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449. , 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619. , 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 812, 8, 8, 8, 8, 8, 8, 8, 3 , 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 913, 9
    • Når forsøg på at dividere er langsommere end de mere sofistikerede metoder, er det stadig effektivt for mindre tal. Selv når man tester større tal, er det ikke ualmindeligt at tjekke de små tal først, før man skifter til de mere avancerede metoder.

    Fornødenheder

    • Papir, pen, blyant og/eller en lommeregner til træning

    Оцените, пожалуйста статью