Počet primárních dělitelů čísla. Kolik dělitelů má primární číslo?

Každý školák ví, že všechna čísla jsou rozdělena na jednoduché a složené. Navíc ti, kteří usilovně studují matematiku, jsou známí a jejich vlastnosti. Jestliže však odpověď na otázku, kolik dělitelů má číslo prvního čísla, je skrytá ve samotné definici tohoto pojmu, pak je poměrně obtížné určit počet primárních dělitelů pro danou. Vyřeší se metodou vyhledávání a pravděpodobnostních algoritmů implementovaných v počítači.

Trochu historie

Je známo, že starí Řekové byli první, kdo studoval vlastnosti prvočísel. Nicméně jejich existence byla známa již několik tisíciletí předtím, než Aristotle obsahoval věty o svých vlastnostech ve slavných "Principech". Starověcí Řekové vynalezli a síto Eratosthenes, což je algoritmus pro nalezení primárních čísel z intervalu [1, n].

V 17. století došlo k průlomu ve studiu Pierre Fermat a Maren Mersenne. První formulovaná věta, později pojmenovaná po něm, podle níž jsou všechny čísla formuláře 2²ⁿ - jednoduché, prokázat to pro n = 1..4. Následně Leonard Euler prokázal, že pro n = 5 je získáno složené číslo. Souběžně s tím Maren Mersenne vybrala jednoduchá čísla formuláře 2^str - 1, kde p je primární. Jsou zajímavé tím, že je pro ně snadné ověřit dodržování kritéria jednoduchosti. Vzhledem k této skutečnosti se čísla Mersenne používají k identifikaci velmi velkých čísel. V současné době omezuje známou podobnost jako 2^77232917 minus-1.

Navíc jsou široce používány při vývoji generátorů náhodných čísel, které mají v praxi široké uplatnění.

Legendre a Gauss také hráli důležitou roli ve studiu primárních čísel. Tito vědci předložili hypotézu o jejich hustotě.

Eratosthenesové síto

Pokud můžeme okamžitě zavolat prvních dělitelů čísla 4, pak pro velkých čísel je to obvykle obtížné. O řešení tohoto problému začali lidé myslet před několika tisíci lety. Zejména, Starověký řecký matematik Eratosthenes, který žil na křižovatce třetího a druhého století před naším letopočtem přišel s algoritmem pro nalezení všech prvočísel méně než celé číslo n.

To bylo nazýváno sítem, protože se "zvedá" nebo moderním způsobem "filtrová" všechna čísla kromě jednoduchých.

Tento algoritmus se skládá z následujících příkazů:

1. napište všechna celá čísla od 2 do n;
2. přiřadit proměnnou p hodnotu 2, protože toto je nejmenší primární číslo;
3. vyškrtnout v seznamu všechna čísla od 2p do n, násobky p;
4. přiřadit hodnotu proměnné p na hodnotu prvního, neškrceného čísla zaznamenané sekvence, která je větší než p;
5. opakujte 3. a 4. co nejdéle.

Pokud je vše správně provedeno, pak v seznamu nebudou všechny přední čísla od dvou do n překročeny.

Pro realizaci síta Eratosthenes na elektronickém počítači se používá modernizovaný algoritmus. Ve třetím kroku můžete vyškrtnout čísla začínající číslem p₂, jelikož všechny kompozitní čísla, které jsou menší než to, budou již překročeny. Potom by mělo dojít k zastavení provozu algoritmu, pokud je podmínka p₂n.

Měli bychom také vzít v úvahu, že všechny přední čísla, s výjimkou dvojice, jsou liché, takže od p2 můžete "filtrovat" 2p.

Hlavní teorém aritmetiky

Podle definice má hlavní dva rozdělovače. Jeden z nich je 1 a druhý je hodnota samotná.

Předtím, než zjistíme, jaký je počet primárních dělitelů čísla, stojí za to věnovat trochu času studovat základní teorém aritmetiky. Podle toho může být přirozené číslo n> 1 reprezentováno jako n = p₁* hellip- sdot- * p_k, kde p₁, hellip-, str_m Jsou to primární čísla. Navíc je takové vyjádření jedinečné až po řadu sekvencí jeho kofaktorů.

Důsledek této věty lze formulovat následovně: libovolné přirozené číslo n může být reprezentováno ve formě n = p₁^d1* str₂^d2 * * * hellip- * p_k^dm (v jiné formulaci: kanonický rozklad čísla n na jednoduché faktory má formu n = p₁^d1* str₂^d2* sdot- hellip-sdot- * p_k^dm), kde p₁₂< hellip- _m Jsou primární čísla a d₁, hellip-, d_mJsou nějaké přirozená čísla.

Kromě toho, již víte, základní aritmetické teorém lze parafrázovat takto: všechna kanonická dekompozice n lze považovat za totožné, ne-li dávat pozor na pořadí přepážkami. To znamená, že pro velké množství čísel existuje mnoho poměrně jednoduchých algoritmů pro jejich rozklad na primární faktory, které nakonec přinesou stejný výsledek.

Kritérium jednoduchosti

Než zjistíme, jak lze nalézt největšího prvního dělitele čísla (NAP) n, je třeba se zabývat další důležitou otázkou.

Takže zjistěte, jakým algoritmem je možné zjistit, zda existují i ​​jiní dělitelé než jednotka a její vlastní.

To lze provést vyčíslením prvních čísel p₁, hellip-p_k. A cyklus může být ukončen, jakmile p_{i + 1}, pro které bylo ověření provedeno, splní podmínku (pi₊₁).² n.

Vysvětlete, proč může být busta omezena na p_i= sqr (n).

Předpokládejme, že číslo n, studované pro jednoduchost, má nějakého dělitele p. Pak d = n / p bude také jeho dělitel. Protože d a p jsou různá čísla, žádný z nich nemůže být větší než kořen n.

Jak najít největšího prvního dělitele čísla n

Najděte NPD n, můžete, postupujte podle následujícího schématu:

• Rozdělte n na dvě, pokud je rovno nebo tři, pokud je zvláštní. Jediná výjimka je n, poslední číslice v desítkové notaci je nula nebo pět. Takové číslo lze okamžitě rozdělit na pět.
• Pokud výsledek není celé číslo, dělíme n následujícími celočíselnými čísly, třídíme je na p_i= sqr (n).

Nad výsledným číslem n₁ proveďte všechny akce ve stejném pořadí jako výše, pouze s podmínkou p_i= sqr (n₁).

Pokud v některém z kroků vyhledávání n₁ není rozdělen do jedné z primes, pak n je celé číslo a je jeho vlastní NAP. V opačném případě získáme n₂ a pokračujte v rozdělení s hledáním až do okamžiku, kdy v kroku (i + 1) vytvoříme n_i - celku.

Příklad:

Najdeme nejdůležitějších dělitelů čísla 276.

• rozdělit na dvě;
• získáme 138;
• protože číslo je rovnoměrné, pak opět rozdělíme o "dva";
• výsledek je 69;
• rozdělit na další číslo "tři";
• získáme 23.

Jelikož je toto číslo jednoduché, můžeme shrnout. Jednoduché děliče 276 jsou 2, 3 a 23.

Jak zjistit počet primárních dělitelů čísla

Pokud mluvíme o zcela malém počtu, řešení tohoto problému není obtížné. Zvažme konkrétní příklad. Najdeme nejdůležitějších dělitelů čísla 54.

Postupujte takto:

• 54 rozdělit na "dva" a získat 27;
• 27 je liché, takže ji již nerozdělujeme do "dvou", ale na další číslo, tj. "Tři";
• že 27 = 3³;
• Rozklad 54 má tedy tvar 54 = 2¹ * 3³, tj. primární dělitelé čísla 54 jsou "dva" a "tři".

Nicméně to není vše, co jsme chtěli vědět. Nyní najdeme počet primárních dělitelů čísla 54. Je rovno výsledku mocnin prvotních faktorů kanonického rozkladu čísla n = p₁* * *^d1 str₂^d2* sdot- hellip-sdot- * p_m^dm, zvýšení o 1. Jinými slovy, ve všeobecném případě K = (d₁+1) * ... * (d_m+1).

Pak pro S4 máme K = 2 * 4 = 8, to znamená, že celkový počet dělitelů je osm.

Všimněte si, že všechno se stalo mnohem jednodušším, kdybychom mluvili o 23, 37, 103 atd., Protože každý ví, kolik dělitelů má první číslo.

Příklad:

Najděte počet prvních dělitelů 9990.

• protože číslo 9990 končí číslem "nula", pak je rozdělen na pět a dva.
• máme 999.
• v důsledku třídění máme 333;
• opět rozdělíme tři, dostaneme 111;
• rozdělit tři, máme 37;
• 37 je primární číslo, protože není dělitelné bez zbytku žádnou z prvočíselných čísel, které jsou mezi dvojicí a kořenem čísla 37;
• počítáme počet prvních deliterů čísla 9990. Jde o 2,3,5 a 37, tedy jenom čtyři.

Problém velkých čísel

Protože není divné, problém nalezení všech prvotních faktorů čísla je poměrně komplikovaný. Faktem je, že až dosud jsme zvažovali pouze čísla, jejichž desetinná notace se skládala z jednoho až čtyř znaků. Pro ně jsou všechny výpočty prováděny v několika krocích a mohou být naprosto přemoženy, mají jen pero a list papíru po ruce. Situace je jiná, pokud jde například o 1000místné číslo. Najdete-li všechny své hlavní faktory, bude trvat víc než miliardu let, i když bude zapojen nejmocnější superpočítač na světě.

Jednoduchá čísla a ochrana informací

Každý moderní člověk, který má možnosti, které vznikly díky vzniku lokálních počítačových sítí a internetu je třeba chránit důvěrnost jejich osobních údajů, e-mailů a tak dále. Pro tento účel se používají kryptografické algoritmy veřejného klíče.

V systémech s desítkami a stovkami uživatelů je správa klíčů vážným problémem. Aby se zabránilo tomu, že klíčové informace zvládnou útočníka, je nutné do šifrovacího procesu zavést nějakou náhodnou hodnotu.

Pro tento účel používají nejběžnější algoritmy RSA velké počáteční čísla.

Existuje pouze 10151 primárních čísel 1 až 512 bitů. Současně pro čísla, která jsou blízko n, pravděpodobnost, že náhodně zvolené číslo bude jednoduché, je 1 / ln n. Celkový počet prvočísel, který je menší než n, je tedy n / ln n. To naznačuje, že je extrémně nepravděpodobné, že si 2 lidé vyberou stejné velké číslo.

Test Miller-Rabina

Pro kryptografické účely se často používá tento druh definice jednoduchosti čísla, který má několik úprav.

Test Miller-Rabina je založen na testování řady podmínek provedených pro čísla, která se dělí pouze o 1 a do sebe. Pokud je porušena alespoň jedna z požadavků, je toto číslo "zkoušky" rozpoznáno jako složené.

Pro daný m jsou liché celá čísla t a s taková, že m-1 = 2^st.

Náhodné číslo a je zvoleno tak, že 1

Důsledkem Věty Rabin je skutečnost, že v případě, čísla R, které jsou vybrány náhodně, svědky uznány pro určování primality m, pak pravděpodobnost, že je kompozitní, nesmí přesáhnout (4^-r).

Nyní víte, kolik dělitelů má primární číslo a jak zjistit nejprimitivnější algoritmus pro výpočet NAP. Tyto znalosti vám pomohou při řešení mnoha praktických problémů.