Število glavnih delilnikov števila. Koliko divizorjev ima glavno številko?

Vsak učenec ve, da so vse številke razdeljene na preproste in sestavljene. Še več, tisti, ki skrbno preučujejo matematiko, so znani in njihovi lastnosti. Če pa je odgovor na vprašanje o tem, koliko deliteljev ima glavno število, skrit v sami definiciji tega pojma, potem je težko določiti število glavnih delilcev za dano. Rešuje se z uporabo metode iskanja in verjetnostnih algoritmov, ki se izvajajo na računalniku.

Malo zgodovine

Znano je, da so bili stari Grki prvi, ki so preučevali lastnosti prvih števil. Vendar pa je bil njihov obstoj znan več tisočletij, preden je Aristotel vključil teoreme o svojih lastnostih v svoje znane "načela". Stari Grki so izumili in sito Eratostena, ki je algoritem za iskanje prvih števil iz intervala [1, n].

V 17. stoletju so naredili preboj v svoji študiji Pierre Fermat in Maren Mersenne. Prvi je oblikoval izrek, pozneje imenovan po njem, po katerem so vse številke oblike 2²ⁿ - enostavna, dokazuje, da je n = 1..4. Vendar pa je kasneje Leonard Euler pokazal, da je za n = 5 dobljeno sestavljeno število. Vzporedno s tem je Maren Mersenne izbrala preproste številke obrazca 2^str - 1, kjer je p prime. Zanimive so, ker jim je enostavno preveriti skladnost z merilom enostavnosti. Glede na to dejstvo se številke Mersenne uporabljajo za identifikacijo super velikih primehtnih števil. Trenutno je omejitev znanih podob 2^77232917 minus-1.

Poleg tega se pogosto uporabljajo pri razvoju generatorjev naključnih števil, ki imajo v praksi široko uporabo.

Legenda in Gauss sta imela tudi pomembno vlogo pri proučevanju prvih števil. Ti znanstveniki podajajo hipotezo o njihovi gostoti.

Eratosthenes sieve

Če lahko takoj pokličemo glavne delilce števila 4, potem pa za veliko število to je običajno težko storiti. O rešitvi tega problema so ljudje začeli razmišljati pred nekaj tisoč leti. Še posebej, Grški matematik Eratosteni, ki je živel na prelomu tretje in druge stoletja pred Kristusom, je pripravil algoritem za iskanje vseh prime števil manj kot celo število n.

To je bilo imenovano sito, ker "odmakne" ali sodobno "filtrira" vse številke, razen preprostih.

Algoritem sestavljajo naslednji ukazi:

1. napišite vsa cela števila od 2 do n;
2. določi spremenljivko p vrednost 2, saj je to najmanjša prime številka;
3. na seznamu preseči vse številke od 2p do n, večkratniki p;
4. določi vrednost spremenljivke p na vrednost prvega, ne presečenega števila posnetega zaporedja, ki je večji od p;
5. ponovite tretji in četrti čim dlje.

Če je vse opravljeno pravilno, potem na seznamu ne bodo prečrtane vse prime številke od dveh do n.

Za izvedbo sita Eratosteni na elektronskem računalniku se uporablja posodobljen algoritem. Na tretjem koraku lahko prečkate številke, ki se začnejo s številko p₂, saj bodo vse sestavljene številke, ki so manjše od tega, že prešle. Nato se mora ustaviti delovanje algoritma, ko je pogoj p₂n.

Prav tako je treba upoštevati, da so vsa primarna števila, z izjemo dvojca, neparna, zato se lahko začnete s p2, lahko "filtrirate" za 2p.

Glavna izreka aritmetike

Po definiciji ima primež dva ločila. Eden od njih je 1, druga pa je vrednost sam.

Preden ugotovite, koliko je število glavnih delilcev števila, je vredno vzeti nekaj časa, da preučimo osnovno izrečno izjavo aritmetike. Glede na to je naravno število n> 1 lahko predstavljeno kot n = p₁* hellip- sdot- * p_k, kjer je str₁, hellip-, str_m So prvotne številke. Poleg tega je takšna predstavitev edinstvena glede na zaporedje njenih kofaktorjev.

Sledi te teoreme lahko formuliramo na naslednji način: vsako naravno število n lahko predstavimo v obliki n = p₁^d1* str₂^d2 * hellip- * p_k^dm (v drugi formulaciji: kanonična razgradnja števila n v preproste faktorje ima obliko n = p₁^d1* str₂^d2* sdot- hellip-sdot- * p_k^dm), kjer je str₁₂< hellip- _m Ali so prime številke in d₁, hellip-, d_mJe nekaj naravnih števil.

Poleg tega že veste osnovno aritmetično izrek lahko parafraziral takole: vsaka kanonično razgradnja n mogoče šteti za enake, če ne bodite pozorni na vrstni red delilniki. To pomeni, da v praksi za precejšnje število številk obstaja veliko precej preprostih algoritmov za njihovo razgradnjo v prime faktorje, ki sčasoma prinašajo enak rezultat.

Kriterij preprostosti

Preden ugotovite, kako najde največji glavni delilnik števila (NAP) n, se mora obravnavati še eno pomembno težavo.

Torej, ugotovimo, s katerim algoritmom je mogoče ugotoviti, ali obstajajo drugi deli, razen enote in lastne.

To lahko storite z nabiranjem prvih številk str₁, hellip-p_k. In cikel se lahko zaključi takoj, ko str_{i + 1}, za katerega je bilo opravljeno preverjanje, izpolnjuje pogoj (pi₊₁)² n.

Razložimo, zakaj je zlom lahko omejeno na str_i= sqr (n).

Recimo, da ima število n, preučeno za preprostost, nekaj delitelja p. Nato bo d = n / p tudi njen delitelj. Ampak, ker sta d in p različna števila, nobena od njih ne more biti večja od korena n.

Kako najti največji primarni delilnik števila n

Poiščite NPD n, lahko pa delate v skladu z naslednjo shemo:

• Razdelite n na dve, če je celo ali tri, če je čudno. Edina izjema je n, zadnja cifra v decimalnem zapisu je nič ali pet. Takšno številko lahko takoj razdelimo na pet.
• Če rezultat ni celo število, delite n s temi celi števili, jih razvrstite na str_i= sqr (n).

Preko nastale številke n₁ opravi vsa dejanja v enakem vrstnem redu kot zgoraj, samo s pogojem p_i= sqr (n₁).

Če na katerem koli koraku iskanja n₁ ni razdeljen na enega od prvin, potem je n celo število in je lasten NAP. V nasprotnem primeru dobimo n₂ in nadaljujemo delitev z iskanjem do trenutka, ko na stopnji (i + 1) ugotovimo, da je n_i - celotno.

Primer:

Najdemo glavne delilce številke 276.

• deliti z "dva";
• dobimo 138;
• saj je število enakomerno, nato pa ponovno razdelimo z "dva";
• Rezultat je 69;
• deliti z naslednjim glavnim številom "trije";
• dobimo 23.

Ker je ta številka preprosta, lahko povzamemo. Preprosti delilci 276 so 2, 3 in 23.

Kako najti število glavnih delilcev števila

Če govorimo o celotnem majhnem številu, potem rešitev te težave ni težka. Poglejmo konkreten primer. Najdemo glavne delilce števila 54.

Za to:

• 54 delijo z "dva" in dobijo 27;
• 27 je čuden, zato ga ne delimo več v "dve", temveč na naslednje glavno število, to je "tri";
• da je 27 = 3³;
• Tako ima razgradnja 54 obliko 54 = 2¹ * 3³, tj. glavni delilci številke 54 so "dve" in "trije".

Vendar to ni vse, kar smo želeli vedeti. Sedaj najdemo število primarnih delilcev števila 54. Enak je produkt moči glavnih dejavnikov kanonične razgradnje števila n = p₁*^d1 str₂^d2* sdot- hellip-sdot- * p_m^dm, povečal za 1. Z drugimi besedami, v splošnem primeru K = (d₁+1) * ... * (d_m+1).

Potem za S4 imamo K = 2 * 4 = 8, to pomeni, da je skupno število delilcev osem.

Upoštevajte, da je vse postalo veliko preprostejše, če govorimo o 23, 37, 103 itd., Saj vsi vedo, koliko divizorjev ima največje število.

Primer:

Poiščite število glavnih delilcev 9990.

• saj se številka 9990 konča s številko "nič", potem je razdeljena na pet in dve.
• imamo 999.
• zaradi delitve s tremi imamo 333;
• ponovno razdelimo za tri, dobimo 111;
• delimo s tremi, imamo 37;
• 37 je glavno število, ker ni deljivo brez preostanka s katerim koli prvim številom, ki so med dvojico in korenom števila 37;
• štejemo število glavnih delilcev številke 9990. To sta 2,3,5 in 37, kar pomeni, da jih je le štiri.

Problem velikih števil

Ker ni čudno, je težava pri iskanju vseh glavnih dejavnikov števila precej zapletena. Dejstvo je, da smo do sedaj upoštevali le številke, katerih decimalna oznaka je bila sestavljena iz enega do štirih znakov. Za njih so vsi izračuni izvedeni v več korakih in jih je mogoče povsem prevrniti, saj imajo samo pero in list papirja. Stanje je drugačno, na primer pri 1000-mestni številki. Če želite poiskati vse svoje glavne dejavnike, bo trajalo več kot milijardo let, tudi če bo vključen najmočnejši superračunalnik na svetu.

Preproste številke in zaščita informacij

Vsak sodoben človek, ki uživa priložnosti, ki so se pojavile po zaslugi pojava lokalnih računalniških omrežij in interneta mora varovati zaupnost svojih osebnih podatkov, e-pošte in tako naprej. V ta namen uporabite kriptografskih ključnih algoritmov javne.

V sistemih z desetimi in na stotine uporabnikov je ključno upravljanje resen problem. Da bi ključnim informacijam preprečili obvladovanje napadalca, je treba v postopek šifriranja uvesti nekaj naključnih vrednosti.

V ta namen najpogostejši RSA algoritmi uporabljajo velike prime številke.

Obstaja le 10151 primarnih številk od 1 do 512 bitov v dolžini. Hkrati, za številke, ki so blizu n, je verjetnost, da bo naključno izbrana številka preprosta, 1 / ln n. Tako je skupno število prime števila, ki je manjše od n, enako n / ln n. To kaže, da je zelo malo verjetno, da bo dvakrat izbralo enako veliko glavno številko.

Test Miller-Rabin

Za kriptografske namene se pogosto uporablja ta vrsta opredelitve enostavnosti števila, ki ima več sprememb.

Test Miller-Rabin temelji na testiranju številnih pogojev, ki se izvajajo za številke, ki se delijo samo za 1 in vase. Če je kršena vsaj ena od zahtev, je ta "izpitni" številka priznana kot sestavljena.

Za določen m so čudna celo število t in s tako, da je m-1 = 2^st.

Potem se izbere naključno število a, tako da je 1

Posledica Theorem Rabin je dejstvo, da če je R številke, ki so izbrani naključno, priča priznan za določanje praštevilskosti od m, potem je verjetnost, da je kompozit, ne more preseči (4^-r).

Sedaj veste, koliko deliteljev ima glavno številko in kako najti najbolj primitivni algoritem za izračun NAP-jev. To znanje vam bo pomagalo pri reševanju številnih praktičnih problemov.