Čo neznamená prvočíslo? Ako určiť prvočíslo
V tomto článku budeme skúmať prvočísla a zložené čísla. Najprv uvedieme definície prvočísel a zložených čísel a tiež uvedieme príklady. Potom to dokážeme základné čísla nekonečne veľa. Ďalej si napíšeme tabuľku prvočísel a zvážime metódy na zostavenie tabuľky prvočísel, pričom osobitnú pozornosť venujeme metóde nazývanej Eratosthenovo sito. Na záver poukážeme na hlavné body, ktoré je potrebné vziať do úvahy pri dokazovaní, že dané číslo je prvočíslo alebo zložené.
Navigácia na stránke.
Prvočísla a zložené čísla – definície a príklady
Koncepty prvočísel a zložených čísel sa vzťahujú na čísla, ktoré sú väčšie ako jedna. Takéto celé čísla sa v závislosti od počtu ich kladných deliteľov delia na prvočísla a zložené čísla. Takže pochopiť definície prvočísel a zložených čísel, musíte dobre rozumieť tomu, čo sú deliteľ a násobky.
Definícia.
základné čísla sú celé čísla, veľké jednotky, ktoré majú iba dvoch kladných deliteľov, konkrétne seba a 1.
Definícia.
Zložené čísla sú celé čísla, veľké, ktoré majú aspoň troch kladných deliteľov.
Samostatne si všimneme, že číslo 1 sa nevzťahuje na prvočísla ani na zložené čísla. Jednotka má iba jedného kladného deliteľa, ktorým je samotné číslo 1. Toto odlišuje číslo 1 od všetkých ostatných kladných celých čísel, ktoré majú aspoň dvoch kladných deliteľov.
Vzhľadom na to, že kladné celé čísla sú , a že jedno má iba jedného kladného deliteľa, môžeme uviesť iné formulácie uvedených definícií prvočísel a zložených čísel.
Definícia.
základné čísla sú prirodzené čísla, ktoré majú iba dvoch kladných deliteľov.
Definícia.
Zložené čísla sú prirodzené čísla, ktoré majú viac ako dvoch kladných deliteľov.
Všimnite si, že každé kladné celé číslo väčšie ako jedna je buď prvočíslo, alebo zložené číslo. Inými slovami, neexistuje jediné celé číslo, ktoré by nebolo ani prvočíslo, ani zložené. Vyplýva to z vlastnosti deliteľnosti, ktorá hovorí, že čísla 1 a a sú vždy deliteľmi ľubovoľného celého čísla a.
Na základe informácií v predchádzajúcom odseku môžeme uviesť nasledujúcu definíciu zložených čísel.
Definícia.
Voláme prirodzené čísla, ktoré nie sú prvočísla zložený.
Dajme si príklady prvočísel a zložených čísel.
Príklady zložených čísel zahŕňajú 6, 63, 121 a 6 697. Toto vyhlásenie si tiež vyžaduje objasnenie. Číslo 6 má okrem kladných deliteľov 1 a 6 aj deliteľov 2 a 3, keďže 6 = 2 3, preto je 6 skutočne zložené číslo. Pozitívne faktory 63 sú čísla 1, 3, 7, 9, 21 a 63. Číslo 121 sa rovná súčinu 11·11, takže jeho kladnými deliteľmi sú 1, 11 a 121. A číslo 6 697 je zložené, keďže jeho kladnými deliteľmi sú okrem 1 a 6 697 aj čísla 37 a 181.
Na záver tohto bodu by som chcel ešte upozorniť na fakt, že prvočísla a druhočísla nie sú ani zďaleka to isté.
Tabuľka prvočísel
Prvočísla sú pre pohodlie ich ďalšieho použitia zaznamenané v tabuľke nazývanej tabuľka prvočísel. Nižšie je tabuľka prvočísel do 1000.
Vynára sa logická otázka: „Prečo sme naplnili tabuľku prvočísel len do 1000, nie je možné vytvoriť tabuľku všetkých existujúcich prvočísel“?
Najprv odpovedzme na prvú časť tejto otázky. Pre väčšinu problémov, ktoré vyžadujú použitie prvočísel, budú postačovať prvočísla do tisícky. V iných prípadoch sa s najväčšou pravdepodobnosťou budete musieť uchýliť k niektorým špeciálnym riešeniam. Hoci tabuľku prvočísel môžeme určite vytvoriť až do ľubovoľne veľkého konečného kladného čísla, či už je to 10 000 alebo 1 000 000 000, v ďalšom odseku si povieme o metódach vytvárania tabuliek prvočísel, najmä sa pozrieme na metódu volal.
Teraz sa pozrime na možnosť (alebo skôr nemožnosť) zostaviť tabuľku všetkých existujúcich prvočísel. Nemôžeme vytvoriť tabuľku všetkých prvočísel, pretože prvočísel je nekonečne veľa. Posledné tvrdenie je veta, ktorú dokážeme po nasledujúcej pomocnej vete.
Veta.
Najmenší kladný deliteľ prirodzeného čísla väčšieho ako jedna je prvočíslo.
Dôkaz.
Nechaj a je prirodzené číslo väčšie ako jedna a b je najmenší kladný deliteľ iného ako jedna. Dokážme, že b je prvočíslo kontradikciou.
Predpokladajme, že b je zložené číslo. Potom existuje deliteľ čísla b (označme ho b 1), ktorý je odlišný od 1 aj b. Ak vezmeme do úvahy aj to, že absolútna hodnota deliteľa nepresahuje absolútnu hodnotu dividendy (vieme to z vlastností deliteľnosti), potom musí byť splnená podmienka 1
Keďže číslo a je deliteľné b podľa podmienky a povedali sme, že b je deliteľné b 1, pojem deliteľnosti nám umožňuje hovoriť o existencii celých čísel q a q 1 takých, že a=b q a b=b 1 q 1 , odkiaľ a= b 1 · (q 1 · q) . Z toho vyplýva, že súčin dvoch celých čísel je celé číslo, potom rovnosť a=b 1 ·(q 1 ·q) udáva, že b 1 je deliteľ čísla a. Berúc do úvahy vyššie uvedené nerovnosti 1
Teraz môžeme dokázať, že prvočísel je nekonečne veľa.
Veta.
Existuje nekonečné množstvo prvočísel.
Dôkaz.
Predpokladajme, že to tak nie je. To znamená, že predpokladajme, že existuje iba n prvočísel a tieto prvočísla sú p 1, p 2, ..., p n. Ukážme, že vždy môžeme nájsť iné prvočíslo, ako je uvedené.
Uvažujme číslo p rovné p 1 ·p 2 ·...·p n +1. Je jasné, že toto číslo sa líši od každého z prvočísel p 1, p 2, ..., p n. Ak je číslo p prvočíslo, potom je veta dokázaná. Ak je toto číslo zložené, potom na základe predchádzajúcej vety existuje prvočíselník tohto čísla (označíme ho p n+1). Ukážme, že tento deliteľ sa nezhoduje so žiadnym z čísel p 1, p 2, ..., p n.
Ak by to tak nebolo, potom by sa podľa vlastností deliteľnosti súčin p 1 ·p 2 ·…·p n delil p n+1. Ale číslo p je tiež deliteľné p n+1, ktoré sa rovná súčtu p 1 ·p 2 ·...·p n +1. Z toho vyplýva, že p n+1 musí deliť druhý člen tohto súčtu, ktorý sa rovná jednej, ale to nie je možné.
Je teda dokázané, že vždy sa dá nájsť nové prvočíslo, ktoré nie je zahrnuté v žiadnom počte vopred určených prvočísel. Preto je prvočísel nekonečne veľa.
Takže vzhľadom na to, že prvočísel je nekonečne veľa, pri zostavovaní tabuliek prvočísel sa vždy zhora obmedzíte na nejaké číslo, väčšinou 100, 1000, 10000 atď.
Eratosthenove sito
Teraz budeme diskutovať o spôsoboch vytvárania tabuliek prvočísel. Predpokladajme, že potrebujeme vytvoriť tabuľku prvočísel do 100.
Najzrejmejšou metódou riešenia tohto problému je postupná kontrola kladných celých čísel, počínajúc 2 a končiacimi 100, na prítomnosť kladného deliteľa, ktorý je väčší ako 1 a menší ako testované číslo (z vlastností deliteľnosti vieme že absolútna hodnota deliteľa nepresahuje absolútnu hodnotu dividendy, nenulovú). Ak sa takýto deliteľ nenájde, potom je testované číslo prvočíslo a zapíše sa do tabuľky prvočísel. Ak sa takýto deliteľ nájde, potom je testované číslo zložené, NIE JE zapísané v tabuľke prvočísel. Potom nasleduje prechod na ďalšie číslo, ktoré sa podobne kontroluje na prítomnosť deliteľa.
Poďme si popísať prvých pár krokov.
Začíname číslom 2. Číslo 2 nemá žiadneho kladného deliteľa okrem 1 a 2. Preto je to jednoduché, preto to zapíšeme do tabuľky prvočísel. Tu treba povedať, že 2 je najmenšie prvočíslo. Prejdime k číslu 3. Jeho možný kladný deliteľ iný ako 1 a 3 je číslo 2. Ale 3 nie je deliteľné 2, preto je 3 prvočíslo a je potrebné ho zahrnúť aj do tabuľky prvočísel. Prejdime k číslu 4. Jeho kladnými deliteľmi okrem 1 a 4 môžu byť čísla 2 a 3, skontrolujme ich. Číslo 4 je deliteľné 2, preto je 4 zložené číslo a nie je potrebné ho uvádzať v tabuľke prvočísel. Upozorňujeme, že 4 je najmenšie zložené číslo. Prejdime k číslu 5. Skontrolujeme, či aspoň jedno z čísel 2, 3, 4 je jeho deliteľ. Keďže 5 nie je deliteľné 2, 3 alebo 4, potom je prvočíslo a treba ho zapísať do tabuľky prvočísel. Potom nasleduje prechod na čísla 6, 7 a tak ďalej až do 100.
Tento prístup k zostaveniu tabuľky prvočísel má ďaleko od ideálu. Tak či onak má právo na existenciu. Všimnite si, že pri tejto metóde konštrukcie tabuľky celých čísel môžete použiť kritériá deliteľnosti, ktoré mierne urýchlia proces hľadania deliteľov.
Existuje pohodlnejší spôsob vytvorenia tabuľky prvočísel, tzv. Slovo „sito“ prítomné v názve nie je náhodné, pretože akcie tejto metódy pomáhajú takpovediac „preosiať“ celé čísla a veľké jednotky cez sito Eratosthenes, aby sa oddelili jednoduché od zložených.
Ukážme si Eratosthenovo sito v akcii pri zostavovaní tabuľky prvočísel do 50.
Najprv si zapíšte čísla 2, 3, 4, ..., 50 v poradí.
Prvé napísané číslo, 2, je prvočíslo. Teraz sa od čísla 2 posúvame postupne o dve čísla doprava a tieto čísla škrtáme, kým sa nedostaneme na koniec zostavovanej tabuľky čísel. Tým sa prečiarknu všetky čísla, ktoré sú násobkom dvoch.
Prvé číslo po 2, ktoré nie je prečiarknuté, je 3. Toto číslo je prvočíslo. Teraz sa od čísla 3 postupne posunieme doprava o tri čísla (berúc do úvahy už prečiarknuté čísla) a prečiarkneme ich. Tým sa prečiarknu všetky čísla, ktoré sú násobkom troch.
Prvé číslo po 3, ktoré nie je prečiarknuté, je 5. Toto číslo je prvočíslo. Teraz sa od čísla 5 dôsledne posunieme doprava o 5 čísel (berieme do úvahy aj skôr prečiarknuté čísla) a prečiarkneme ich. Tým sa prečiarknu všetky čísla, ktoré sú násobkami piatich.
Ďalej prečiarkneme čísla, ktoré sú násobkami 7, potom násobkami 11 atď. Proces končí, keď už nie sú žiadne čísla na odčiarknutie. Nižšie je vyplnená tabuľka prvočísel do 50 získaných pomocou Eratosthenovho sita. Všetky neprečiarknuté čísla sú prvočísla a všetky prečiarknuté čísla sú zložené.
Sformulujme a dokážme aj vetu, ktorá urýchli proces zostavovania tabuľky prvočísel pomocou Eratosthenovho sita.
Veta.
Najmenší kladný deliteľ zloženého čísla a, ktorý sa líši od jednotky, nepresahuje , kde je od a .
Dôkaz.
Označme písmenom b najmenšieho deliteľa zloženého čísla a, ktoré je odlišné od jednotky (číslo b je prvočíslo, ako vyplýva z vety dokázanej na samom začiatku predchádzajúceho odseku). Potom existuje celé číslo q také, že a=b·q (tu q je kladné celé číslo, čo vyplýva z pravidiel násobenia celých čísel) a (pre b>q je porušená podmienka, že b je najmenším deliteľom a , keďže q je tiež deliteľ čísla a kvôli rovnosti a=q·b ). Vynásobením oboch strán nerovnosti kladným a celým číslom väčším ako jedna (toto je nám dovolené) dostaneme , z ktorého a .
Čo nám dáva osvedčená veta o Eratosthenovom sitku?
Po prvé, prečiarknutie zložených čísel, ktoré sú násobkami prvočísla b, by malo začínať číslom rovným (to vyplýva z nerovnosti). Napríklad prečiarknutie čísel, ktoré sú násobkom dvoch, by malo začínať číslom 4, násobky troch číslom 9, násobky piatich číslom 25 atď.
Po druhé, zostavenie tabuľky prvočísel až po číslo n pomocou Eratosthenovho sita možno považovať za úplné, ak všetky zložené čísla, ktoré sú násobkami prvočísel, nepresahujú . V našom príklade n=50 (keďže robíme tabuľku prvočísel do 50), a preto by Eratosthenovo sito malo eliminovať všetky zložené čísla, ktoré sú násobkami prvočísel 2, 3, 5 a 7, ktoré nepresiahne aritmetickú druhú odmocninu 50. To znamená, že už nemusíme hľadať a preškrtávať čísla, ktoré sú násobkami prvočísel 11, 13, 17, 19, 23 a tak ďalej až do 47, keďže už budú prečiarknuté ako násobky menších prvočísel 2. 3, 5 a 7.
Je toto číslo prvočíslo alebo zložené?
Niektoré úlohy vyžadujú zistenie, či je dané číslo prvočíslo alebo zložené. Vo všeobecnosti táto úloha nie je ani zďaleka jednoduchá, najmä pri číslach, ktorých písanie pozostáva z veľkého počtu znakov. Vo väčšine prípadov musíte hľadať nejaký konkrétny spôsob, ako to vyriešiť. My sa však pokúsime nasmerovať myšlienkový pochod pre jednoduché prípady.
Samozrejme, môžete skúsiť použiť testy deliteľnosti, aby ste dokázali, že dané číslo je zložené. Ak napríklad nejaký test deliteľnosti ukáže, že dané číslo je deliteľné nejakým kladným celým číslom väčším ako jedna, potom je pôvodné číslo zložené.
Príklad.
Dokážte, že 898,989,898,989,898,989 je zložené číslo.
Riešenie.
Súčet číslic tohto čísla je 9·8+9·9=9·17. Keďže číslo rovnajúce sa 9·17 je deliteľné 9, potom pomocou deliteľnosti 9 môžeme povedať, že pôvodné číslo je deliteľné aj 9. Preto je zložený.
Významnou nevýhodou tohto prístupu je, že kritériá deliteľnosti neumožňujú dokázať prvoradosť čísla. Preto pri testovaní čísla, aby ste zistili, či je prvočíslo alebo zložené, musíte robiť veci inak.
Najlogickejší prístup je vyskúšať všetky možné delitele daného čísla. Ak žiadny z možných deliteľov nie je skutočným deliteľom daného čísla, potom toto číslo bude prvočíslo, inak bude zložené. Z teorém dokázaných v predchádzajúcom odseku vyplýva, že deliče daného čísla a treba hľadať medzi prvočíslami nepresahujúcimi . Dané číslo a možno teda postupne deliť prvočíslami (ktoré sa dajú pohodlne prevziať z tabuľky prvočísel), pričom sa snažíme nájsť deliteľa čísla a. Ak sa nájde deliteľ, potom číslo a je zložené. Ak medzi prvočíslami nepresahujúcimi , nie je deliteľ čísla a, potom číslo a je prvočíslo.
Príklad.
číslo 11 723 jednoduché alebo zložené?
Riešenie.
Poďme zistiť, do akého prvočísla môžu byť deliče čísla 11 723. Aby sme to urobili, poďme hodnotiť.
To je celkom zrejmé 
, od roku 200 2 = 40 000 a 11 723<40 000
(при необходимости смотрите статью porovnanie čísel). Možné hlavné faktory 11 723 sú teda menšie ako 200. Už to nám značne uľahčuje úlohu. Ak by sme to nevedeli, museli by sme prejsť všetkými prvočíslami nie do 200, ale do čísla 11 723.
V prípade potreby môžete presnejšie vyhodnotiť. Pretože 108 2 = 11 664 a 109 2 = 11 881, potom 108 2<11 723<109 2
, следовательно, 
. Akékoľvek z prvočísel menších ako 109 je teda potenciálne prvočíslo daného čísla 11 723.
Teraz postupne rozdelíme číslo 11 723 na prvočísla 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. Ak je číslo 11 723 delené jedným zo zapísaných prvočísel, bude zložené. Ak nie je deliteľné žiadnym zo zapísaných prvočísel, tak pôvodné číslo je prvočíslo.
Nebudeme popisovať celý tento monotónny a monotónny proces delenia. Povedzme hneď, že 11 723
Vyčíslenie deliteľov. Podľa definície číslo n je prvočíslo iba vtedy, ak nie je rovnomerne deliteľné 2 a inými celými číslami okrem 1 a samého seba. Vyššie uvedený vzorec odstraňuje zbytočné kroky a šetrí čas: napríklad po kontrole, či je číslo deliteľné 3, nie je potrebné kontrolovať, či je deliteľné 9.
- Funkcia floor(x) zaokrúhli x na najbližšie celé číslo, ktoré je menšie alebo rovné x.
Získajte informácie o modulárnej aritmetike. Operácia „x mod y“ (mod je skratka latinského slova „modulo“, teda „modul“) znamená „vydeliť x y a nájsť zvyšok“. Inými slovami, v modulárnej aritmetike, pri dosiahnutí určitej hodnoty, ktorá je tzv modul, čísla sa opäť „otočia“ na nulu. Napríklad hodiny udržiavajú čas s modulom 12: ukazujú 10, 11 a 12 hodín a potom sa vrátia na 1.
- Mnoho kalkulačiek má mod kľúč. Koniec tejto časti ukazuje, ako manuálne vyhodnotiť túto funkciu pre veľké čísla.
Prečítajte si o úskaliach Fermatovej Malej vety. Všetky čísla, pre ktoré nie sú splnené podmienky testu, sú zložené, ale zostávajúce čísla sú len pravdepodobne sú klasifikované ako jednoduché. Ak sa chcete vyhnúť nesprávnym výsledkom, hľadajte n v zozname "Carmichaelových čísel" (zložené čísla, ktoré vyhovujú tomuto testu) a "pseudoprvočísla Fermat" (tieto čísla spĺňajú podmienky testu len pre niektoré hodnoty a).
Ak je to vhodné, použite Miller-Rabinov test. Hoci je táto metóda dosť ťažkopádna na ručný výpočet, často sa používa v počítačových programoch. Poskytuje prijateľnú rýchlosť a produkuje menej chýb ako Fermatova metóda. Zložené číslo nebude akceptované ako prvočíslo, ak sa výpočty robia pre viac ako ¼ hodnôt a. Ak náhodne vyberiete rôzne hodnoty a a u všetkých z nich test poskytne pozitívny výsledok, môžeme s pomerne vysokou mierou istoty predpokladať, že n je prvočíslo.
Pre veľké čísla použite modulárnu aritmetiku. Ak nemáte po ruke kalkulačku s modom, alebo vaša kalkulačka nie je navrhnutá tak, aby zvládala také veľké čísla, použite na uľahčenie výpočtov vlastnosti mocnin a modulárnej aritmetiky. Nižšie je uvedený príklad pre 3 50 (\displaystyle 3^(50)) mod 50:
- Prepíšte výraz do vhodnejšej formy: mod 50. Pri manuálnych výpočtoch môžu byť potrebné ďalšie zjednodušenia.
- (3 25 ∗ 3 25) (\displaystyle (3^(25)*3^(25))) mod 50 = mod 50 mod 50) mod 50. Tu sme brali do úvahy vlastnosť modulárneho násobenia.
- 3 25 (\displaystyle 3^(25)) mod 50 = 43.
- (3 25 (\displaystyle (3^(25)) mod 50 ∗ 3 25 (\displaystyle *3^(25)) mod 50) mod 50 = (43 ∗ 43) (\displaystyle (43*43)) mod 50.
- = 1849 (\displaystyle =1849) mod 50.
- = 49 (\displaystyle =49).
Čísla sú rôzne: prirodzené, racionálne, racionálne, celé a zlomkové, kladné a záporné, komplexné a prvočíslo, nepárne a párne, reálne atď. Z tohto článku sa dozviete, čo sú prvočísla.
Aké čísla sa v angličtine nazývajú „jednoduché“?
Školáci veľmi často nevedia odpovedať na jednu z na prvý pohľad najjednoduchších otázok v matematike, čo je prvočíslo. Často si mýlia prvočísla s prirodzenými číslami (teda číslami, ktoré ľudia používajú pri počítaní predmetov, pričom v niektorých zdrojoch začínajú nulou a v iných jednotkou). Ale to sú úplne dva odlišné pojmy. Prvočísla sú prirodzené čísla, teda celé čísla a kladné čísla, ktoré sú väčšie ako jedna a majú iba 2 prirodzených deliteľov. Navyše jeden z týchto deliteľov je dané číslo a druhý je jedna. Napríklad tri je prvočíslo, pretože ho nemožno bezo zvyšku deliť iným číslom, ako je samo sebou a jednotkou.
Zložené čísla
Opakom prvočísel sú zložené čísla. Sú tiež prirodzené, tiež väčšie ako jedna, ale nemajú dvoch, ale väčší počet deliteľov. Takže napríklad čísla 4, 6, 8, 9 atď. sú prirodzené, zložené, ale nie prvočísla. Ako vidíte, ide väčšinou o párne čísla, ale nie o všetky. Ale „dva“ je párne číslo a „prvé číslo“ v rade prvočísel.
Následná sekvencia
Na zostavenie série prvočísel je potrebné vybrať zo všetkých prirodzených čísel, berúc do úvahy ich definíciu, to znamená, že musíte konať protirečivo. Je potrebné preskúmať každé z kladných prirodzených čísel, či má viac ako dvoch deliteľov. Skúsme zostaviť rad (sekvenciu), ktorý pozostáva z prvočísel. Zoznam začína dvoma, po ktorých nasledujú tri, keďže je deliteľný iba sebou a jedným. Zvážte číslo štyri. Má iné delitele ako štyri a jedna? Áno, to číslo je 2. Štyri teda nie je prvočíslo. Päť je tiež prvočíslo (nie je deliteľné žiadnym iným číslom okrem 1 a 5), ale šesť je deliteľné. A vo všeobecnosti, ak budete sledovať všetky párne čísla, všimnete si, že okrem „dvoch“ žiadne z nich nie je prvočíslo. Z toho usudzujeme, že párne čísla, okrem dvoch, nie sú prvočísla. Ďalší objav: všetky čísla deliteľné tromi, okrem samotných troch, či už párnych alebo nepárnych, tiež nie sú prvočísla (6, 9, 12, 15, 18, 21, 24, 27 atď.). To isté platí pre čísla, ktoré sú deliteľné piatimi a siedmimi. Celý ich počet tiež nie je jednoduchý. Poďme si to zhrnúť. Jednoduché jednociferné čísla teda zahŕňajú všetky nepárne čísla okrem jednej a deviatky a párne „dvojky“ sú párne čísla. Samotné desiatky (10, 20,... 40 atď.) nie sú jednoduché. Dvojciferné, trojciferné atď. prvočísla možno určiť na základe vyššie uvedených zásad: ak nemajú iných deliteľov okrem seba a jedného.
Teórie o vlastnostiach prvočísel
Existuje veda, ktorá študuje vlastnosti celých čísel vrátane prvočísel. Toto je odvetvie matematiky nazývané vyššie. Okrem vlastností celých čísel sa zaoberá aj algebraickými a transcendentálnymi číslami, ako aj funkciami rôzneho pôvodu súvisiacimi s aritmetikou týchto čísel. V týchto štúdiách sa okrem elementárnych a algebraických metód využívajú aj analytické a geometrické metódy. Konkrétne „Teória čísel“ sa zaoberá štúdiom prvočísel.
Prvočísla sú „stavebnými kameňmi“ prirodzených čísel
V aritmetike existuje teorém nazývaný základná veta. Podľa nej môže byť akékoľvek prirodzené číslo okrem jedného reprezentované ako súčin, ktorého činiteľmi sú prvočísla a poradie činiteľov je jedinečné, čo znamená, že jedinečný je aj spôsob zobrazenia. Nazýva sa to rozklad prirodzeného čísla na prvočísla. Tento proces má aj iný názov – rozklad čísel. Na základe toho možno prvočísla nazvať „stavebný materiál“, „bloky“ na vytváranie prirodzených čísel.
Hľadajte prvočísla. Testy jednoduchosti
Mnoho vedcov z rôznych čias sa snažilo nájsť nejaké princípy (systémy) na nájdenie zoznamu prvočísel. Veda pozná systémy nazývané Atkinovo sito, Sundarthamovo sito a Eratosthenove sito. Neprinášajú však žiadne významné výsledky a na zistenie prvočísel sa používa jednoduchý test. Matematici tiež vytvorili algoritmy. Zvyčajne sa nazývajú testy primality. Existuje napríklad test, ktorý vyvinuli Rabin a Miller. Používajú ho kryptografi. Existuje aj test Kayal-Agrawal-Sasquena. Napriek dostatočnej presnosti je však veľmi náročný na výpočet, čo znižuje jeho praktický význam.
Má množina prvočísel nejaký limit?
Staroveký grécky vedec Euclid napísal vo svojej knihe „Elementy“, že množina prvočísel je nekonečno. Povedal toto: „Predstavme si na chvíľu, že prvočísla majú limit. Potom ich medzi sebou vynásobme a jednu pridajme k produktu. Číslo získané ako výsledok týchto jednoduchých akcií nemožno deliť žiadnym zo série prvočísel, pretože zvyšok bude vždy jedna. To znamená, že existuje nejaké ďalšie číslo, ktoré ešte nie je zahrnuté v zozname prvočísel. Náš predpoklad preto nie je pravdivý a táto množina nemôže mať limit. Okrem Euklidovho dôkazu existuje modernejší vzorec, ktorý dal švajčiarsky matematik z 18. storočia Leonhard Euler. Podľa nej recipročný súčet súčtu prvých n čísel neobmedzene rastie s pribúdajúcim číslom n. A tu je vzorec vety o rozdelení prvočísel: (n) rastie ako n/ln (n).
Aké je najväčšie prvočíslo?
Ten istý Leonard Euler dokázal nájsť najväčšie prvočíslo svojej doby. To je 2 31 - 1 = 2147483647. Do roku 2013 však bolo vypočítané ďalšie najpresnejšie najväčšie v zozname prvočísel - 2 57885161 - 1. Nazýva sa Mersennovo číslo. Obsahuje asi 17 miliónov desatinných číslic. Ako vidíte, číslo nájdené vedcom z osemnásteho storočia je niekoľkonásobne menšie ako toto. Malo to tak byť, pretože Euler tento výpočet vykonával ručne, pričom nášmu súčasníkovi zrejme pomáhal počítač. Toto číslo bolo navyše získané na matematickej fakulte jednej z amerických katedier. Čísla pomenované po tomto vedcovi prešli testom primality Luc-Lemaire. Veda sa však pri tom nechce zastaviť. Nadácia Electronic Frontier Foundation, ktorá bola založená v roku 1990 v Spojených štátoch amerických (EFF), ponúkla peňažnú odmenu za nájdenie veľkých prvočísel. A ak sa do roku 2013 cena udeľovala tým vedcom, ktorí ich našli medzi 1 a 10 miliónmi desatinných čísel, dnes toto číslo dosahuje od 100 miliónov do 1 miliardy. Ceny sa pohybujú od 150 do 250 tisíc amerických dolárov.
Názvy špeciálnych prvočísel
Čísla, ktoré boli nájdené vďaka algoritmom vytvoreným určitými vedcami a prešli testom jednoduchosti, sa nazývajú špeciálne. Tu sú niektoré z nich:
1. Merssen.
4. Cullen.
6. Mills a kol.
Jednoduchosť týchto čísel, pomenovaných podľa vyššie uvedených vedcov, je stanovená pomocou nasledujúcich testov:
1. Luc-Lemaire.
2. Pepina.
3. Riesel.
4. Billhart - Lemaire - Selfridge a ďalší.
Moderná veda pri tom nekončí a svet sa pravdepodobne v blízkej budúcnosti dozvie mená tých, ktorí mohli získať cenu 250 000 dolárov nájdením najväčšieho prvočísla.
Problém 2.30
Dané jednorozmerné pole A pozostávajúce z prirodzených čísel. Zobrazte počet prvočísel v poli.
Najprv vám dovoľte pripomenúť, čo sú prvočísla.
Teraz prejdime k úlohe. V podstate potrebujeme program, ktorý určuje prvočísla. A triediť prvky a kontrolovať ich hodnoty je záležitosťou technológie. Zároveň vieme nielen počítať, ale aj zobraziť prvočísla poľa.
Ako určiť prvočíslo v Pascale
Poskytnem algoritmus riešenia s podrobnou analýzou v jazyku Pascal. Riešenie môžete vidieť vo vzorovom programe v C++.
DÔLEŽITÉ!
Tu sa môže veľa ľudí pokaziť. Definícia hovorí, že prvočíslo má hladké dve rôzne rozdeľovač Preto číslo 1 nie je prvočíslo (ani prvočíslo, pretože nulu možno deliť ľubovoľným číslom).
Či je číslo prvočíslo skontrolujeme pomocou , ktoré si sami vytvoríme. Táto funkcia vráti hodnotu TRUE, ak je číslo prvočíslo.
Vo funkcii najskôr skontrolujeme, či je číslo menšie ako dva. Ak áno, tak to už nie je prvočíslo. Ak je číslo 2 alebo 3, potom je jednoznačne prvočíslo a nie sú potrebné žiadne ďalšie kontroly.
Ale ak je číslo N väčšie ako tri, potom v tomto prípade budeme cyklicky prechádzať všetkými možnými deliteľmi, počnúc od 2 po (N-1). Ak je číslo N deliteľné nejakým deliteľom bezo zvyšku, tak to tiež nie je prvočíslo. V tomto prípade cyklus prerušíme (pretože nemá zmysel ďalej kontrolovať) a funkcia vráti FALSE.
Nemá zmysel kontrolovať, či je číslo deliteľné samo sebou (preto cyklus trvá len do N-1).
Samotnú funkciu tu predstavovať nebudem - pozrite si ju vo vzorových programoch.
Riešenie problému 2.30 v Pascale mytask; //***************************************************** ******************* //KONŠTANTY //********************************** ********* **************************************** POČET = 100; //Počet prvkov v poli //************************************************** *********** ************************* // FUNKCIE A POSTUPY //********** *********************************************************** ** //***** ********************************************* * ******** // Kontroluje, či je číslo prvočíslo // VSTUP: N - číslo // VÝSTUP: TRUE - číslo N je prvočíslo, NEPRAVDA - nie je prvočíslo //********** ********************************************* **** IsPrimeNumber(N: WORD) : ; var i: ; začať := PRAVDA; N z 0..3: začiatok N Koniec; koniec; koniec; i:= 2 až (N-1) urob, ak (N i) = 0 then //Začiatok nie je prvočíslo Výsledok:= FALSE; ; koniec; koniec; i: SLOVO; X: SLOVO = 0; A: z WORD; //***************************************************** **************** // HLAVNÝ PROGRAM //********************************** ************************************ begin //Vyplňte pole číslami pre i:= 1 až COUNT do A[i] := i; //Počítajte a vyberte prvočísla z poľa pre i:= 1 až COUNT urobte if IsPrimeNumber(A[i]) then begin (X); Write(A[i], " "); koniec; (#10#13"Počet prvočísel = ", X); WriteLn("Koniec. Stlačte ENTER..."); ; koniec.
Riešenie problému 2.30 v C++#include
Vyhľadávanie
Môžeme vás informovať o nových článkoch,