Turinys

• Žengti
• 1 metodas iš 4: pabandykite padalyti
• 2 metodas iš 4: mažosios Fermato teoremos naudojimas
• 3 metodas iš 4: naudojant Millerio-Rabino testą
• 4 metodas iš 4: Likusios kinų teoremos naudojimas
• Patarimai
• Būtinybės

Pirminiai skaičiai yra skaičiai, kurie dalijasi tik patys iš savęs ir vadinami 1 - kiti skaičiai junginys numeriai. Kai reikia patikrinti, ar skaičius yra pagrindinis, yra keletas variantų. Kai kurie iš šių metodų yra gana paprasti, bet didesniam skaičiui nėra praktiški. Kiti dažnai naudojami testai yra iš tikrųjų pilni algoritmai, pagrįsti vienu tikimybė kurie kartais klaidingai skaičių laiko pagrindiniu. Perskaitykite 1 žingsnį, kad sužinotumėte, kaip išbandyti save, jei turite reikalų su pirminiu skaičiumi.

Žengti

1 metodas iš 4: pabandykite padalyti

Bandymas padalyti yra pats paprasčiausias būdas išbandyti skaičių. Mažiems skaičiams tai taip pat greičiausias būdas. Testas pagrįstas pirminio skaičiaus apibrėžimu: skaičius yra pagrindinis, jei jis dalijasi tik pats iš savęs ir 1.

1. Tarkim n yra skaičius, kurį norite išbandyti. Padalinkite skaičių n iš visų galimų dalinamųjų sveikųjų skaičių. Didesniems skaičiams, pvz., N = 101, yra nepraktiška padalyti iš bet kokio galimo skaičiaus, mažesnio nei n. Laimei, yra keletas gudrybių, siekiant sumažinti tikrinamų veiksnių skaičių.
2. Nustatykite, ar n net. Visi lyginiai skaičiai yra visiškai dalijami iš 2. Taigi, jei n yra lyginis, galite tai pasakyti n yra sudėtinis skaičius (taigi ir ne pagrindinis skaičius). Norėdami greitai nustatyti, ar skaičius yra lyginis, turite atkreipti dėmesį tik į paskutinį skaitmenį. Jei paskutinis skaitmuo yra 2, 4, 6, 8 arba 0, tai skaičius yra lyginis ir nėra pirminis.
   • Vienintelė šios taisyklės išimtis yra pats skaičius 2, kuris, kadangi jis pats dalijasi ir 1, taip pat yra pagrindinis. 2 yra vienintelis lygus pagrindinis.
3. Dalis n bet kuriuo skaičiumi nuo 2 iki n-1. Kadangi pirminis skaičius neturi kitų veiksnių, išskyrus save ir 1, ir kadangi sveikojo skaičiaus koeficientai yra mažesni už jų sandaugą, patikrinus mažesnio nei n ir didesnio nei 2 sveikojo skaičiaus dalijimąsi, bus nustatyta, ar n yra pagrindinis. Mes pradedame po 2, nes lyginiai skaičiai (2 kartotiniai) negali būti pirminiai skaičiai. Tai toli gražu nėra efektyvus bandymo būdas, kaip pamatysite žemiau.
   • Pavyzdžiui, jei norėtume naudoti šį metodą, norėdami patikrinti, ar 11 yra pagrindinis, ar ne, mes padalytume 11 iš 3, 4, 5, 6, 7, 8, 9 ir 10, ieškodami sveikojo atsakymo be likutinės dalies. Kadangi nė vienas iš šių skaičių visiškai netelpa į 11, galime sakyti, kad 11 yra vienas yra pagrindinis.
4. Norėdami sutaupyti laiko, išbandykite tik iki sqrt (n), suapvalinta iki. Skaičiaus n patikrinimas, patikrinant visus skaičius nuo 2 iki n-1, gali greitai užtrukti daug laiko. Pvz., Jei norėtume patikrinti, ar šiuo metodu 103 yra pagrindinis, turėtume padalyti iš 3, 4, 5, 6, 7 ... ir tt, iki 102! Laimei, bandyti taip nereikia. Praktiškai reikia tik patikrinti veiksnius tarp 2 ir n kvadratinės šaknies. Jei n kvadratinė šaknis nėra skaičius, suapvalinkite ją iki artimiausio sveiko skaičiaus ir išbandykite šį skaičių. Paaiškinimą rasite žemiau.
   • Panagrinėkime koeficientus 100. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2 ir 100 × 1. Atkreipkite dėmesį, kad po 10 × 10 veiksniai yra vienodi jei tai 10 × 10, tik tada apverskite. Apskritai galime nepaisyti n didesnių nei sqrt (n) veiksnių, nes jie yra tiesiog mažesnių nei sqrt (n) veiksnių tęsinys.
   • Pabandykime pavyzdį. Jei n = 37, tada mums nereikia išbandyti visų skaičių nuo 3 iki 36, kad nustatytume, ar n yra pagrindinis. Vietoj to, mes tiesiog turime pažvelgti į skaičius nuo 2 iki sqrt (37) (suapvalinti į viršų).
     • sqrt (37) = 6,08 - apvalinsime tai iki 7.
     • 37 nėra visiškai dalijamasi iš 3, 4, 5, 6 ir 7, todėl galime drąsiai teigti, kad tai yra vienas pirminis skaičius yra.
5. Norėdami sutaupyti dar daugiau laiko, naudojame tik pagrindinius veiksnius. Testavimo procesą galima padalinti dar trumpiau, neįtraukiant tų veiksnių, kurie nėra pirminiai skaičiai. Pagal apibrėžimą kiekvienas sudėtinis skaičius gali būti išreikštas dviejų ar daugiau pirminių skaičių sandauga. Taigi skaičiaus n dalyti iš bendro skaičiaus nereikia - tai tolygu kelis kartus dalijant iš pirminių skaičių. Taigi, mes galime dar labiau susiaurinti galimų veiksnių sąrašą tik iki pirminių skaičių, mažesnio už sqrt (n).
   • Tai reiškia, kad visi lyginiai veiksniai, taip pat veiksniai, kurie yra pirminių skaičių kartotiniai, gali būti praleisti.
   • Pavyzdžiui, pabandykime nustatyti, ar 103 yra pagrindinis, ar ne. Kvadratinė 103 šaknis yra 11 (suapvalinta į viršų). Pirminiai skaičiai nuo 2 iki 11 yra 3, 5, 7 ir 11. 4, 6, 8 ir 10 yra lyginiai, o 9 yra 3 kartotinis, pirminis skaičius, todėl galime jo praleisti. Tai atlikdami mes sumažinome galimų veiksnių sąrašą tik iki 4 skaičių!
     • 103 nėra visiškai skaidomas nei su 3, nei su 5, nei su 7, nei su 11, todėl dabar mes žinome, kad 103 yra vienas pirminis skaičius yra.

2 metodas iš 4: mažosios Fermato teoremos naudojimas

1640 m. Prancūzų matematikas Pierre'as de Fermatas pirmą kartą pasiūlė teoremą (dabar pavadintą jo vardu), kuri gali būti labai naudinga nustatant, ar skaičius yra pagrindinis. Techniškai „Fermat“ testas skirtas patikrinti, ar skaičius yra sudėtinis, o ne pagrindinis. Taip yra todėl, kad testas gali „visiškai užtikrintai“ parodyti, kad skaičius yra sudėtinis, tačiau tik „tikimybė“, kad skaičius yra pagrindinis. Mažoji Fermato teorema yra naudinga tais atvejais, kai bandymas padalyti yra nepraktiškas ir kai yra turimų skaičių sąrašas, kuris yra teoremos išimtis.

1. Tarkim n skaičius skirtas testavimui. Šį testą naudojate norėdami nustatyti, ar nurodytas skaičius n yra pagrindinis. Tačiau, kaip pažymėta aukščiau, ši teorema kartais gali klaidingai apibūdinti kai kuriuos junginius kaip pagrindinius. Svarbu į tai atsižvelgti ir patikrinti savo atsakymą, kuris paaiškinamas toliau.
2. Pasirinkite sveiką skaičių a tarp 2 ir n-1 (imtinai). Tikslus visas jūsų pasirinktas skaičius nėra svarbus. Kadangi a parametrai apima 2 ir n-1, taip pat galite juos naudoti.
   • Pavyzdys: ar 100 geriausių, ar ne. Tarkime, kad mes imamės 3 kaip bandomoji vertė - tai yra nuo 2 iki n-1, taigi to pakanka.
3. apskaičiuoti a (mod n). Norint parengti šią išraišką, reikia šiek tiek išmanyti matematinę sistemą, vadinamą modulinė matematika. Modulinėje matematikoje skaičiai grįžta į nulį pasiekę tam tikrą vertę, dar vadinamą modulis. Tai galite galvoti kaip apie laikrodį: galiausiai laikrodžio rodyklė grįš į 1 valandą po 12 valandos, o ne į 13 valandą. Modulis pažymimas kaip (mod n). Taigi šiame etape apskaičiuojate a, kurio modulis n.
   • Kitas metodas yra apskaičiuoti a, tada padalinti jį iš n, tada likusią dalį naudoti kaip atsakymą. Specializuoti skaičiuotuvai, turintys modulio funkciją, gali būti labai naudingi dalijant didelius skaičius, nes jie gali iškart apskaičiuoti likusią dalybos dalį.
   • Naudodami tokią skaičiuoklę savo pavyzdyje galime pamatyti, kad 3/100 lieka 1. Taigi, 3 (mod 100) yra 1.
4. Jei tai apskaičiuosime ranka, rodiklį naudojame kaip trumpą formatą. Jei neturite skaičiuotuvo su modulio funkcija, naudokite užrašą su rodikliu, kad būtų lengviau nustatyti likusį. Žiūrėkite žemiau:
   • Mūsų pavyzdyje apskaičiuojame 3, kurio modulis yra 100. 3 yra labai, labai didelis skaičius - 515 377 520 732 010 331 036 461 129 765 621 272 702 107 522 001 - toks didelis, kad pasidaro labai sunku dirbti. Užuot naudoję 48 skaitmenų atsakymą 3, geriau parašykite jį kaip eksponentą, taigi (((((((3)*3))))*3)). Atminkite, kad eksponento rodiklio paėmimas turi dauginimo rodiklių poveikį ((x) = x).
     • Dabar mes galime nustatyti likusius dalykus. Pradėkite spręsdami (((((((((3) * 3)))) * * 3)) vidiniame skliaustų rinkinyje ir eikite į kelią, padalydami kiekvieną žingsnį iš 100. Suradę likusius dalykus, tai panaudosime kitame žingsnyje, o ne tikrame atsakyme. Žiūrėkite žemiau:
       • ((((((((9) * 3)))) * * 3)) - 9/100 neturi likutinės dalies, todėl galime tęsti.
       • ((((((27)))) * * 3)) - 27/100 neturi likutinės dalies, todėl galime judėti toliau.
       • (((((729))) * 3)) - 729/100 = 7 R 29. Mūsų likutis yra 29. Mes tęsiame kitą žingsnį, o ne 729.
       • ((((29=841)) * 3)) - 841/100 = 8 R 41. Kitame etape vėl panaudojame likusią 41 dalį.
       • (((41 = 1681) * 3)) - 1681/100 = 16 R 81. Kitame etape mes naudojame likusią 81 dalį.
       • ((81*3 = 243)) - 243/100 = 2 R 43. Likusią 43 dalį panaudosime kitame žingsnyje.
       • (43 = 1849) - 1849/100 = 18 R 49. Likusią 49 dalį panaudosime kitame žingsnyje.
       • 49 = 2401 - 2401/100 = 24 R 1. mūsų galutinis likutis yra 1. Kitaip tariant, 3 (mod 100) = 1. Atkreipkite dėmesį, kad tai yra tas pats atsakymas, kurį apskaičiavome ankstesniame etape!
5. Sužinokite, ar a (mod n) = a (mod n). Jei ne, n yra junginys. Jei tiesa, tada n tikriausiai, (bet nesu tikras) pirminis skaičius. Pakartojus testą su skirtingomis a reikšmėmis, rezultatas gali būti tikresnis, tačiau yra retų sudėtinių skaičių, kurie tenkina Fermato teoremą visi a reikšmės. Tai vadinama Carmichael skaičiais - mažiausias iš šių skaičių yra 561.
   • Mūsų pavyzdyje 3 (mod 100) = 1 ir 3 (mod 100) = 3,1 ≠ 3, taigi galime sakyti, kad 100 yra sudėtinis skaičius.
6. Norėdami įsitikinti savo rezultatu, naudokite „Carmichael“ numerius. Prieš tęsdami žinodami, kurie skaičiai atitinka „Carmichael“ seriją, galite daug nerimauti dėl to, ar skaičius yra pagrindinis. Apskritai „Carmichael“ skaičiai yra atskirų pirminių skaičių sandauga, kur visiems pirminiams skaičiams laikoma, kad jei p yra n daliklis, tai p-1 yra ir n-1 daliklis. Internetinis „Carmichael“ skaičių sąrašas gali būti labai naudingas nustatant, ar skaičius yra pagrindinis, naudojant mažąją Fermato teoremą.
   
   

3 metodas iš 4: naudojant Millerio-Rabino testą

„Miller-Rabin“ testas veikia taip pat, kaip ir mažoji Fermato teorema, tačiau geriau susidoroja su nestandartiniais skaičiais, tokiais kaip „Carmichael“.

1. Tarkim n yra nelyginis skaičius, kurį norime patikrinti dėl pirmumo. Kaip ir aukščiau nurodytais metodais, n yra kintamasis, kurio norime nustatyti pirmumą.
2. Slėgis n-1 forma 2 × d kuriame d yra keista. Skaičius n yra pagrindinis, jei jis nelyginis. Taigi n - 1 turi būti lygus. Kadangi n - 1 yra lyginis, jį galima parašyti kaip du kartus nelyginio skaičiaus galią. Taigi, 4 = 2 × 1; 80 = 2 × 5; ir taip toliau.
   • Tarkime, kad mes norime nustatyti, ar n = 321 yra pagrindinis. 321 - 1 = 320, kurį galime išreikšti kaip 2 × 5.
     • Šiuo atveju n = 321 yra tinkamas skaičius. Norint nustatyti n - 1, kai n = 371, gali prireikti didelės d vertės, todėl vėliau visą procesą bus sunkiau. 371 - 1 = 370 = 2 × 185
3. Pasirinkite bet kurį skaičių a tarp 2 ir n-1. Tikslus jūsų pasirinktas skaičius neturi reikšmės - tiesiog jis turi būti mažesnis nei n ir didesnis nei 1.
   • Mūsų pavyzdyje su n = 321 pasirenkame a = 100.
4. apskaičiuoti a (mod n). Jei a = 1 arba -1 (mod n), tada praeina n Millerio-Rabino testą ir yra tikriausiai pirminis skaičius. Kaip ir mažojoje Fermato teoremoje, šis testas negali visiškai tiksliai nustatyti skaičiaus pirmumo, tačiau reikalauja papildomų bandymų.
   • Mūsų pavyzdyje, kai n = 321, a (mod n) = 100 (mod 321). 100 = 10 000 000 000 (mod 321) = 313. Norėdami rasti likusią 100/321 dalį, mes naudojame specialų skaičiuoklį arba trumpinio metodą su rodikliu, kaip aprašyta anksčiau.
     • Kadangi negavome 1 ar -1, negalime tiksliai pasakyti, kad n yra pagrindinis. Bet vis tiek turime padaryti daugiau - skaitykite toliau.
5. Kadangi rezultatas nėra lygus 1 arba -1, apskaičiuokite a, a, ... ir taip toliau, iki ad. Apskaičiuokite pakeltą iki d kartų galios iki 2. Jei kuri nors iš jų lygi 1 arba -1 (mod n), tada praeina n Milleris-Rabinas išbando ir tikriausiai yra pagrindinis. Jei nustatėte, kad n išlaikė testą, patikrinkite savo atsakymą (žr. Toliau pateiktą žingsnį). Jei n neatitinka nė vieno iš šių testų, tai yra vienas sukomponuotas numeris.
   • Primename, kad mūsų pavyzdyje a reikšmė yra 100, s vertė yra 6 ir d yra 5. Mes tęsiame bandymą, kaip parodyta žemiau:
     • 100 = 1 × 10.
       • 1 × 10 (mod. 321) = 64,64 ≠’ 1 arba -1. Eik ramiai.
     • 100 = 1 × 10.
       • 1 × 10 (mod. 321) = 244,244 ≠ 1 arba -1.
     • Šiuo metu mes galime sustoti. s - 1 = 6 - 1 = 5. Dabar pasiekėme 4d = 2, o 2 kartų d galios žemiau 5d nėra. Kadangi nė vienas iš mūsų skaičiavimų neatsakė į 1 ar -1, galime sakyti, kad n = 321 sukomponuotas skaičius yra.
6. Jei n išlaikė Millerio-Rabino testą, pakartokite kitas reikšmes a. Jei nustatėte, kad n reikšmė gali būti pirminė, bandykite dar kartą naudodami kitą, atsitiktinę a reikšmę, kad patvirtintumėte bandymo rezultatą. Jei n iš tikrųjų yra pagrindinis, tai bus teisinga bet kuriai a reikšmei. Jei n yra sudėtinis skaičius, jis nepavyks tris ketvirtadalius a reikšmių. Tai suteikia jums daugiau tikrumo nei Fermato mažoji teorema, kur sudėtiniai skaičiai („Carmichael“ skaičiai) išlaiko bet kurios a vertės testą.

4 metodas iš 4: Likusios kinų teoremos naudojimas

1. Pasirinkite du skaičius. Vienas iš skaičių nėra pirminis, o antrasis - tai skaičius, kuriam tikrinama pirmumas.
   • „Bandymo numeris1“ = 35
   • 2 bandymo numeris = 97
2. Pasirinkite du duomenų taškus, atitinkamai didesnius nei nulis ir mažesnius nei TestNumber1 ir TestNumber2. Jie negali būti lygūs vienas kitam.
   • Duomenys1 = 1
   • Duomenys2 = 2
3. Apskaičiuokite MMI (matematinis dauginamasis atvirkštinis) bandymų skaičiui1 ir testo skaičiui2
   • Apskaičiuokite MMI
     • MMI1 = bandymo numeris2 ^ -1 Mod bandymo numeris1
     • MMI2 = bandymo numeris1 ^ -1 Mod bandymo numeris2
   • Tik pirminiams skaičiams (bus ne pirminių skaičių rezultatas, bet tai nėra MMI):
     • MMI1 = (TestNumber2 ^ (TestNumber1-2))% TestNumber1
     • MMI2 = (TestNumber1 ^ (TestNumber-2))% TestNumber2
   • Taigi:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. Sukurkite dvejetainę lentelę kiekvienam MMI iki modulio „Log2“
   • Dėl MMI1
     • F (1) = bandymo skaičius2% bandymo skaičius1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% bandymo skaičius1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% bandymo skaičius1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% bandymo skaičius1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% bandymo skaičius1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% bandymo skaičius1 = 1 * 1% 35 = 1
   • Apskaičiuokite „TestNumber1 - 2“ dvejetainį logaritmą
     • 35 -2 = 33 (10001) 2 bazė
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 Mod 35
     • MMI1 = 27
   • Skirta MMI2
     • F (1) = bandymo skaičius1% bandymo skaičius2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% bandymo skaičius2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% bandymo skaičius2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% bandymo skaičius2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% bandymo skaičius2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% bandymo skaičius2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% bandymo skaičius2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% bandymo skaičius2 = 35 * 35 mod 97 = 61
   • Apskaičiuokite „TestNumber2–2“ dvejetainį logaritmą
     • 97 - 2 = 95 = (1011111) 2 pagrindas
     • 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. Apskaičiuoti (Data1 * TestNumber2 * MMI1 + Data2 * TestNumber1 * MMI2)% (TestNumber1 * TestNumber)
   • Atsakymas = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Atsakymas = (2619 + 4270)% 3395
   • Atsakymas = 99
6. Patikrinkite, ar „TestNumber1“ nėra pirminis1
   • Apskaičiuokite (atsakymas - duomenys1)% bandymo skaičių1
   • 99 -1 % 35 = 28
   • Kadangi 28 yra didesnis nei 0, 35 nėra pagrindinis
7. Patikrinkite, ar „TestNumber2“ yra pagrindinis
   • Apskaičiuokite (atsakymas - duomenys2)% bandymo skaičių2
   • 99 - 2 % 97 = 0
   • Kadangi 0 yra lygus 0, 97 yra galimas pirminis skaičius
8. Pakartokite 1–7 veiksmus dar bent du kartus.
   • Jei 7 veiksmas lygus 0:
     • Naudokite kitą „TestNumber1“, jei „TestNumber1“ nėra pagrindinis.
     • Naudokite kitą „TestNumber1“, kur „TestNumber1“ iš tikrųjų yra pagrindinis. Tokiu atveju 6 ir 7 žingsniai yra lygūs 0.
     • Duomenims1 ir duomenims2 naudokite skirtingus duomenų taškus.
   • Jei 7 žingsnis visada lygus 0, tikimybė, kad skaičius 2 yra pagrindinis skaičius, yra labai didelė.
   • 1–7 žingsniai yra neteisingi tam tikrais atvejais, kai pirmasis skaičius nėra pirminis, o antrasis yra pirminio skaičiaus, kuris nėra pirminis skaičius „Test Number1“. Tai veikia visais atvejais, kai abu skaičiai yra svarbiausi.
   • 1–7 žingsniai kartojami todėl, kad yra keli scenarijai, kai, net jei „TestNumber1“ nėra pirminis ir „TestNumber2“ nėra pagrindinis, bet kuris iš 7 veiksmo skaičius vis tiek yra nulis. Šios būklės yra retos. Pakeitus TestNumber1 kitu ne pirminiu skaičiumi, jei TestNumber2 nėra pagrindinis, TestNumber2 nebebus lygus nuliui, atliekant 7 veiksmą. Išskyrus atvejį, kai „TestNumber1“ yra „TestNumber2“ koeficientas, pirminiai skaičiai visada bus nulis. 7 žingsnis.

Patarimai

• 168 pirminiai skaičiai iki 1000 yra: 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
• Bandant skirstyti lėčiau nei sudėtingesniems metodams, jis vis tiek efektyvus mažesniems skaičiams. Net bandant didesnius skaičius, neretai prieš pereinant prie pažangesnių metodų pirmiausia reikia patikrinti mažus skaičius.

Būtinybės

• Popierius, rašiklis, pieštukas ir (arba) skaičiuoklė treniruotėms