Broj glavnih razdjelnika broja. Koliko razdjelnika ima premijera?

Svaki učenik zna da su svi brojevi podijeljeni na jednostavne i složene. Štoviše, oni koji marljivo proučavaju matematiku, poznati su i njihova svojstva. Međutim, ako je odgovor na pitanje koliko djelitelja ima premijera broj skriven u samoj definiciji tog koncepta, onda je prilično teško odrediti broj glavnih djelitelja za određenu. Riješen je pomoću metode pretraživanja i probabilističkih algoritama implementiranih na računalu.

Malo povijesti

Poznato je da su stari Grci prvi proučavali svojstva premijera. Ipak, njihovo postojanje bilo je poznato već nekoliko tisućljeća prije nego što je Aristotel uključivao teoreme o njihovim svojstvima u svojim slavnim "Principima". Stari Grci su izmislili i sita Eratostena, što je algoritam za pronalaženje primarnih brojeva iz intervala [1, n].

U 17. stoljeću napravljen je proboj u svojoj studiji Pierre Fermat i Maren Mersenne. Prvi je formulirao teorem, koji je kasnije dobio ime po njemu, prema kojemu su svi brojevi oblika 2²ⁿ - jednostavan, dokazujući je za n = 1..4. Međutim, naknadno je Leonard Euler pokazao da za n = 5 dobiva se kompozitni broj. Paralelno s tim, Maren Mersenne izdvojio je jednostavne brojeve obrasca 2^p - 1, u kojem je p premijera. Zanimljivi su u tome što im je lako provjeriti usklađenost s kriterijem jednostavnosti. S obzirom na tu činjenicu, Mersenne brojevi se koriste za prepoznavanje velikih velikih brojeva. Trenutačno ograničenje poznatog izgleda 2^77232917 minus- 1.

Osim toga, oni su naširoko koristi u razvoju generatora slučajnih brojeva koji imaju široku primjenu u praksi.

Legendre i Gauss također su odigrali važnu ulogu u proučavanju prvih brojeva. Ti su znanstvenici postavili hipotezu o njihovoj gustoći.

Eratostenske sita

Ako odmah možemo nazvati premijerno podijeljene brojeve 4, a zatim za velik broj to je obično teško to učiniti. O rješenju ovog problema ljudi su počeli razmišljati prije nekoliko tisuća godina. Posebno, Drevni grčki matematičar Eratoshenes, koji je živio na prijelazu trećeg i drugog stoljeća prije Krista, došao je s algoritmom za pronalaženje svih premijera manje od cjelobrojnog n.

Nazvan je sita, jer "podiže" ili, na moderan način, "filtrira" sve brojeve osim jednostavnih.

Algoritam se sastoji od sljedećih naredbi:

1. napiši sve cijele brojeve od 2 do n;
2. dodijeliti varijablu p vrijednost 2, budući da je to najmanji premijski broj;
3. preskočiti na popisu sve brojeve od 2p do n, višekratnici p;
4. dodijeliti vrijednost varijable p na vrijednost prvog, ne prekoračenog broja snimljene sekvence koja je veća od p;
5. ponovite 3. i 4. koliko god je to moguće.

Ako je sve ispravno izvedeno, na popisu se neće izvući svi premijski brojevi od dva do n.

Za primjenu sita Eratosthenes na elektroničkom računalu, koristi se modernizirani algoritam. U trećem koraku možete prelaziti brojeve počevši od broja p₂, budući da će svi kompozitni brojevi koji su manji od njega, do tog vremena već prekriženi. Tada treba zaustaviti rad algoritma kada se stanje p₂br.

Treba također uzeti u obzir da su svi premijeri, osim izuzetaka, čudni, dakle, počevši od p2, možete "filtrirati" pomoću 2p.

Glavni teorem aritmetike

Po definiciji, premijera ima dva razdjelnika. Jedan od njih je 1, a drugi je vrijednost sama.

Prije pronalaženja broja preostalih djelitelja broja, vrijedi malo vremena da se proučava osnovni teorem aritmetičkog. Prema njemu, prirodni broj n> 1 može se prikazati kao n = p₁* hellip- sdot- * p_k, gdje p₁, hellip-, str_m Jesu li premijeri. Štoviše, takva je reprezentacija jedinstvena do redoslijeda niza njegovih kofaktora.

Korelacija ovog teorema može se formulirati na sljedeći način: svaki prirodni broj n može biti predstavljen u obliku n = p₁^D1* str₂^d2 * hellip- * str_k^dm (u drugoj formulaciji: kanonska dekompozicija broja n u jednostavne čimbenike ima oblik n = p₁^D1* str₂^d2* sdot- hellip-sdot- * str_k^dm), gdje str₁₂< hellip- _m Su brojevi premijera, i d₁, hellip-, d_mJesu li neki prirodni brojevi.

Osim toga, osnovni teorem aritmetike koji je već poznat može se preformulirati na sljedeći način: bilo koja kanonska razgradnja n može se smatrati identičnom ako se ne obazire na redoslijed djelitelja. To znači da u praksi, za značajan broj brojeva, postoji mnogo prilično jednostavnih algoritama za njihovo raspadanje u prve čimbenike, što na kraju daje isti rezultat.

Kriterij jednostavnosti

Prije pronalaženja načina na koji se može pronaći najveći sudionik broja (NAP) n mora se nositi s još jednim važnim pitanjem.

Dakle, doznajemo po kojem je algoritmu moguće utvrditi postoje li drugi razdjelnici osim jedinice i vlastite.

To se može učiniti brojevima brojeva brojeva₁, hellip-p_k. A ciklus se može prekinuti čim p_{i + 1}, za koji je provjera izvršena, zadovoljit će stanje (pi₊₁)² br.

Objasnimo zašto se busting može ograničiti na p_ja= sqr (n).

Pretpostavimo da je broj n, koji se proučavao zbog jednostavnosti, da ima neki djelitelj p. Tada će d = n / p također biti njegov odjeljak. No, budući da d i p su različiti brojevi, niti jedan od njih ne može biti veći od korijena n.

Kako pronaći najveći sudionik broja n

Pronađite NPD n, možete djelovati prema sljedećoj shemi:

• Podijelite n na dva, ako je čak i tri, ako je neparan. Jedina je iznimka n, zadnja znamenka decimalnog zapisa je nula ili pet. Takav se broj može odmah podijeliti na pet.
• Ako rezultat nije cijeli broj, podijelite n sljedećim brojevima, poredajte ih na p_ja= sqr (n).

Preko rezultirajućeg broja n₁ obaviti sve radnje u istom redoslijedu kao gore, samo uz uvjet p_ja= sqr (n₁).

Ako, na bilo kojem od koraka pretraživanja, n₁ nije podijeljen u jedan od primes, tada je n cijeli broj i njegov je vlastiti NAP. Inače, dobivamo n₂ i nastaviti podjelu s pretraživanjem do trenutka kad u (i + 1) koraku ustanovimo da n_ja - cijelu.

primjer

Neka nam pronađemo glavne divizore u broju 276.

• podijeli s "dva";
• dobivamo 138;
• budući da je brojčan, pa opet podijelite s "dva";
• rezultat je 69;
• podijeliti po sljedećem premijeru broj "tri";
• dobivamo 23.

Budući da je ovaj broj jednostavan, možemo sažeti. Jednostavni razdjeljivači 276 su 2, 3 i 23.

Kako pronaći broj premijera razdjelnika broja

Ako govorimo o malom broju, rješenje takvog problema nije teško. Razmotrimo konkretan primjer. Neka nam nađemo glavne divizore broj 54.

Da biste to učinili:

• 54 podijeliti s "dva" i dobiti 27;
• 27 je čudno, tako da ga više ne podijelimo u "dva", već na sljedeći premijski broj, to jest "tri";
• primjećujemo da je 27 = 3³;
• Dakle, dekompozicija 54 ima oblik 54 = 2¹ * 3³, odnosno glavni razdjelnici broja 54 su "dva" i "tri".

Međutim, to nije sve što smo htjeli znati. Sada nalazimo broj glavnih djelitelja broja 54. To je jednak proizvodu ovlasti primarnih čimbenika kanonske razgradnje broja n = p₁*^D1 p₂^d2* sdot- hellip-sdot- * str_m^dm, povećana za 1. Drugim riječima, u općem slučaju K = (d₁+1) * ... * (d_m+1).

Tada za S4 imamo K = 2 * 4 = 8, tj. Ukupan broj razdjelnika je osam.

Imajte na umu da je sve postalo puno jednostavnije ako govorimo o 23, 37, 103, itd., Jer svatko zna koliko raspodjelitelja ima premijera.

primjer

Pronađite broj glavnih djelitelja 9990.

• jer broj 9990 završava brojem "nula", tada je podijeljen na pet i dva.
• imamo 999.
• kao rezultat razdiobe po tri, imamo 333;
• ponovno dijele po tri, dobivamo 111;
• podijeli s tri, imamo 37;
• 37 je premijerski broj, budući da se ne može dijeliti bez preostalih od bilo kojeg od prvih brojeva koji su između poteza i korijena broja 37;
• brojimo premijere od broja 9990. To su 2,3,5 i 37, tj. samo ih četiri.

Problem velikih brojeva

Budući da nije čudno, problem pronalaženja svih čimbenika čiji je broj broj je prilično složen. Činjenica je da smo do sada razmotrili samo brojeve čiji je decimalni zapis sastojao od jednog do četiri znaka. Za njih su svi izračuni izvedeni u nekoliko koraka i mogu se potpuno nadjačati, imaju samo olovku i list papira pri ruci. Situacija je drugačija kada se radi o, na primjer, 1000-znamenkasti broj. Da biste pronašli sve glavne faktore, potrebno je više od milijardu godina, čak i ako će biti uključeni najmoćniji superračunalo na svijetu.

Jednostavni brojevi i zaštita informacija

Svaka moderna osoba koja koristi prilike koje su nastale zbog pojave lokalnih računalnih mreža i Interneta, treba zaštititi privatnost svojih osobnih podataka, e-pošte itd. U tu svrhu koriste se kriptografski algoritmi s javnim ključem.

U sustavima s desecima i stotinama korisnika, ključno upravljanje je ozbiljan problem. Da biste spriječili ključne informacije da se masterirate napadačem, potrebno je uvesti neke slučajne vrijednosti u postupak šifriranja.

U tu svrhu najčešći RSA algoritmi koriste velike premijske brojeve.

Postoji samo 10151 premijera od 1 do 512 bita. Istovremeno, za brojeve koji su blizu n, vjerojatnost da će slučajno odabrani broj biti jednostavna je 1 / ln n. Dakle, ukupni broj premijera koji je manji od n je jednak n / ln n. To sugerira da je krajnje nevjerojatno da će 2 osobe odabrati isti veliki premijerski broj.

Miller-Rabin test

Za kriptografske svrhe često se koristi ova vrsta definicije jednostavnosti broja, koja ima nekoliko modifikacija.

Miller-Rabin test temelji se na testiranju brojnih uvjeta izvedenih za brojeve koji se dijele samo 1 i na sebe. Ako se prekrši barem jedan od uvjeta, ovaj broj "ispita" prepoznaje se kao spoj.

Za određeni m postoje čudni brojevi t i s tako da m-1 = 2^at.

Zatim se odabire nasumični broj a, tako da: 1

Posljedica je Rabinovog teorema činjenica da ako se r brojevi koji su slučajno odabrani prepoznaju kao svjedoci za određivanje jednostavnosti broja m, tada vjerojatnost da je kompozit ne može prijeći (4^-r).

Sada znate koliko razdjelnika ima premijera i kako pronaći najprimitivniji algoritam za izračun NAP-a. Ovo znanje će vam pomoći u rješavanju mnogih praktičnih problema.