Numărul primilor divizori ai unui număr. Câți divizori are un număr prime?

Fiecare școală știe că toate numerele sunt împărțite în simple și compuse. Mai mult decât atât, cei care studiază cu sârguință matematică, sunt cunoscuți și proprietățile lor. Cu toate acestea, dacă răspunsul la întrebarea câte divizori are un număr prime este ascuns în însăși definiția acestui concept, atunci este destul de dificil să se determine numărul primilor divizori pentru un anumit număr. Este rezolvată folosind metoda de căutare și algoritmi probabilisti implementați pe un computer.

Un pic de istorie

Este bine cunoscut faptul că vechii greci au fost primii care au studiat proprietățile numerelor prime. Cu toate acestea, existența lor era cunoscută de mai multe milenii înainte ca Aristotel să includă teoreme asupra proprietăților lor în faimoasele "Principii". Grecii antici au inventat și sita lui Eratosthenes, care este un algoritm pentru găsirea numerelor prime din intervalul [1, n].

În secolul al XVII-lea un progres în studiul lor făcut Pierre Fermat și Maren Mersenne. Prima teorema formulată, denumită ulterior după el, conform căreia toate numerele formularului 2²ⁿ - simplu, dovedind pentru n = 1..4. Cu toate acestea, ulterior, Leonard Euler a arătat că pentru n = 5 se obține un număr compozit. În paralel cu aceasta, Maren Mersenne a evidențiat numere simple ale formularului 2^p - 1, în care p este prime. Ele sunt interesante prin faptul că le este ușor să verifice respectarea criteriului de simplitate. Având în vedere acest fapt, numerele Mersenne sunt folosite pentru a identifica numerele prime super-mari. În prezent, limitarea cunoscutului arata ca 2^77232917 minus- 1.

În plus, ele sunt utilizate pe scară largă în dezvoltarea generatoarelor de numere aleatoare care au o aplicare largă în practică.

Legendre și Gauss au jucat, de asemenea, un rol important în studiul numerelor prime. Acești oameni de știință au prezentat o ipoteză despre densitatea lor.

Eritosthenes sieve

Dacă putem apela imediat primii divizori ai numărului 4, atunci pentru numere mari este de obicei dificil să faceți acest lucru. Despre soluționarea acestei probleme, oamenii au început să se gândească acum câteva mii de ani. În special, Matematician grec vechi Eratosthenes, care a trăit la începutul celui de-al treilea și al doilea secol înaintea lui Hristos, a venit cu un algoritm pentru a găsi toate numerele prime mai puțin decât un întreg n.

S-a numit sita, deoarece "se ridică" sau, într-un mod modern, "filtrează" toate numerele, cu excepția celor simple.

Algoritmul constă din următoarele comenzi:

1. scrie toate numerele întregi de la 2 la n;
2. atribuiți variabilei p o valoare de 2, deoarece acesta este cel mai mic număr prime;
3. să traverseze în listă toate numerele de la 2p la n, multipli de p;
4. aloca valoarea variabilei p la valoarea primului, nu depășit, a secvenței înregistrate care este mai mare decât p;
5. repetați 3 și 4 cât mai mult posibil.

Dacă totul se face corect, atunci în listă toate numerele prime de la două la n nu vor fi depășite.

Pentru a implementa sita Eratosthenes pe un calculator electronic, se utilizează un algoritm modernizat. În al treilea pas, puteți trece numerele începând cu numărul p₂, din moment ce toate numerele compozite care sunt mai mici decât acesta, în acest moment vor fi deja depășite. Apoi, oprirea funcționării algoritmului ar trebui să apară atunci când condiția p₂n.

De asemenea, trebuie să luăm în considerare faptul că toate numerele prime, cu excepția lui deuce, sunt ciudate, prin urmare, începând cu p2, puteți "filtra" cu 2p.

Principala teoremă a aritmeticii

Prin definiție, un prim are doi divizori. Unul dintre ele este 1, iar al doilea este valoarea însăși.

Înainte de a afla care este numărul primilor divizori ai unui număr, merită să luați puțin timp pentru a studia teorema de bază a aritmeticii. Potrivit acestuia, numărul natural n> 1 poate fi reprezentat ca n = p₁* hellip- sdot- * p_k, unde p₁, hellip-, p_m Sunt numere prime. Mai mult, o astfel de reprezentare este unică până la ordinea succesiunii cofactorilor săi.

Corolarul acestei teoreme poate fi formulat după cum urmează: orice număr natural n poate fi reprezentat în forma n = p₁^d1* p₂^d2 * hellip- * p_k^dm (într-o altă formulare: descompunerea canonică a numărului n în factori simpli are forma n = p₁^d1* p₂^d2* sdot- hellip-sdot- * p_k^dm), unde p₁₂< hellip- _m Sunt numere prime și d₁, hellip-, d_mSunt niște numere naturale.

În plus, știi deja teorema aritmetice de bază poate fi parafrazat după cum urmează: orice descompunere canonică a n poate fi considerată ca fiind identice, în cazul în care nu acorde atenție la ordinea de separatoare. Aceasta inseamna ca, in practica, pentru un numar semnificativ de numere, exista multi algoritmi destul de simpli pentru descompunerea lor in factori primari, care in cele din urma produc acelasi rezultat.

Criteriul de simplitate

Înainte de a afla cum se poate găsi cel mai mare divizor principal al unui număr (NAP) n, trebuie să ne ocupăm de o altă problemă importantă.

Deci, să aflăm prin ce algoritm este posibil să stabilim dacă există alți divizori, alții decât o unitate și al ei.

Acest lucru se poate face prin enumerarea numerelor prime p₁, hellip-p_k. Iar ciclul poate fi terminat imediat ce p_{i + 1}, pentru care a fost efectuată verificarea, va satisface condiția (pi₊₁)² n.

Să explicăm de ce bustarea poate fi limitată la p_eu= sqr (n).

Să presupunem că numărul n, studiat pentru simplitate, are un divizor p. Atunci d = n / p va fi și divizorul său. Dar, deoarece d și p sunt numere diferite, niciuna dintre ele nu poate fi mai mare decât o rădăcină a n.

Cum se găsește cel mai mare divizor prim al numărului n

Găsiți NPD n, puteți, acționând în conformitate cu următoarea schemă:

• Împarte n în două, dacă este chiar sau trei, dacă este ciudat. Singura excepție este n, ultima cifră din notația zecimală este zero sau cinci. Un astfel de număr poate fi imediat împărțit în cinci.
• Dacă rezultatul nu este un număr întreg, împărțiți n cu următoarele numere întregi, sortându-le până la p_eu= sqr (n).

Peste numărul rezultat n₁ efectuați toate acțiunile în aceeași ordine ca mai sus, numai cu condiția p_eu= sqr (n₁).

Dacă, în oricare dintre pașii căutării, n₁ nu este împărțit în unul dintre primii, atunci n este un număr întreg și este propriul NAP. În caz contrar, obținem n₂ și continuăm diviziunea cu o căutare până în momentul în care pe pasul (i + 1) stabilim că n_eu - întregul.

exemplu

Să găsim primii divizori ai numărului 276.

• împărțiți cu "doi";
• obținem 138;
• deoarece numărul este egal, apoi divizați din nou cu "doi";
• rezultatul este de 69;
• împărțiți cu următorul număr prim "trei";
• obținem 23.

Din moment ce acest număr este simplu, putem rezuma. Divizorii simpli 276 sunt 2, 3 și 23.

Cum se găsește numărul primilor divizori ai unui număr

Dacă vorbim despre un număr foarte mic, soluția unei astfel de probleme nu este dificilă. Să luăm în considerare un exemplu concret. Să găsim primii divizori ai numărului 54.

Pentru a face acest lucru:

• 54 împărțiți cu "două" și obțineți 27;
• 27 este ciudat, deci nu îl împărțim în "doi", ci la următorul număr prime, adică "trei";
• observăm că 27 = 3³;
• Astfel, descompunerea 54 are forma 54 = 2¹ * 3³, și anume primii divizori ai numărului 54 sunt "doi" și "trei".

Totuși, acest lucru nu este tot ce am vrut să știm. Acum găsim numărul primilor divizori ai numărului 54. Este egal cu produsul puterilor primilor factori ai descompunerii canonice a numărului n = p₁*^d1 p₂^d2* sdot- hellip-sdot- * p_m^dm, majorat cu 1. Cu alte cuvinte, în cazul general K = (d₁+1) * ... * (d_m+1).

Apoi pentru S4 avem K = 2 * 4 = 8, adică numărul total de divizori este de opt.

Rețineți că totul a devenit mult mai simplu dacă am vorbi despre 23, 37, 103 etc., deoarece toată lumea știe câți divizori are un număr prime.

exemplu

Găsiți numărul primilor divizori ai 9990.

• deoarece numărul 9990 se termină cu numărul "zero", atunci este împărțit în cinci și două.
• avem 999.
• ca urmare a împărțirii cu trei avem 333;
• împărțiți din nou cu trei, obținem 111;
• împărțiți pe trei, avem 37;
• 37 este un număr prime, deoarece nu este divizibil fără restul de oricare dintre numerele prime care se află între leu și rădăcina numărului 37;
• numărăm numărul primilor divizori ai numărului 9990. Acestea sunt 2,3,5 și 37, adică există doar patru dintre ei.

Problema numărului mare

Deoarece nu este ciudat, problema găsirii tuturor factorilor prime ai unui număr este destul de complicată. Faptul este că până acum am luat în considerare numai numere ale căror notații zecimale au constat dintr-unu până la patru caractere. Pentru ei, toate calculele sunt efectuate în mai multe etape și pot fi complet suprasolicitate, având doar un stilou și o foaie de hârtie la îndemână. Situația este diferită atunci când vine vorba, de exemplu, de un număr de 1000 de cifre. Găsirea tuturor factorilor săi primi va dura mai mult de un miliard de ani, chiar dacă va fi implicat cel mai puternic supercomputer din lume.

Numerele simple și protecția informațiilor

Fiecare om modern, care se bucură de oportunitățile care au apărut datorită apariției rețelelor de calculatoare locale și Internetul are nevoie pentru a proteja confidențialitatea datelor personale, e-mail-uri și așa mai departe. În acest scop, utilizați algoritmi cheie criptografice publice.

În sistemele cu zeci și sute de utilizatori, managementul cheie este o problemă serioasă. Pentru a împiedica informațiile cheie să stăpânească un atacator, este necesar să introduceți o valoare aleatorie în procesul de criptare.

În acest scop, algoritmii cei mai frecvenți RSA folosesc numere prime mari.

Există doar 10151 prime numere de la 1 până la 512 biți în lungime. În același timp, pentru numerele apropiate de n, probabilitatea ca un număr aleator ales să fie simplă este 1 / ln n. Astfel, numărul total de numere prime care este mai mic decât n este egal cu n / ln n. Acest lucru sugerează că este foarte puțin probabil ca 2 persoane să aleagă același număr de primă mare.

Testul Miller-Rabin

În scopuri criptografice, se folosește adesea acest tip de definiție a simplității unui număr, care are mai multe modificări.

Testul Miller-Rabin se bazează pe testarea unui număr de condiții efectuate pentru numere care se împart numai cu 1 și în ele însele. Dacă este încălcat cel puțin una dintre cerințe, acest număr de examinare este recunoscut ca compus.

Pentru un anumit m există numere impare t și s astfel încât m-1 = 2^sT.

Apoi se alege un număr aleatoriu a, astfel încât 1

Un corolar al teoremei Rabin este faptul că, în cazul în care numerele r, care sunt selectate în mod aleatoriu, asistat recunoscut pentru determinarea primality de m, atunci probabilitatea ca este compozit, nu poate depăși (4^-r).

Acum știi câți divizori au un număr prime și cum să afli algoritmul cel mai primitiv pentru calcularea PNA. Aceste cunoștințe vă vor ajuta să rezolvați multe probleme practice.