Ülesanne 2.30
Antud ühemõõtmeline massiiv A, mis koosneb naturaalarvudest. Kuva kogus algarvud massiivi.
Esiteks lubage mul teile meelde tuletada, mis on algarvud.
Liigume nüüd ülesande juurde. Põhimõtteliselt vajame programmi, mis määrab algarvud. Ja elementide sorteerimine ja nende väärtuste kontrollimine on tehnoloogia küsimus. Samal ajal ei saa me mitte ainult lugeda, vaid ka kuvada massiivi algnumbreid.
Kuidas Pascalis algarvu määrata
Lahendusalgoritm koos üksikasjalik analüüs Ma annan selle Pascalis. Lahendust näete näidisprogrammis C++ keeles.
TÄHTIS!
See on koht, kus paljud inimesed võivad valesti minna. Definitsioon ütleb, et algarvul on sile kaks erinevat jagaja Seetõttu ei ole arv 1 algarvuga (ka mitte algarvuga, kuna nulli saab jagada mis tahes arvuga).
Kontrollime, kas arv on algarvu, kasutades , mille loome ise. See funktsioon tagastab TRUE, kui arv on algarv.
Funktsioonis kontrollime esmalt, kas arv on väiksem kui kaks. Kui jah, siis pole see enam algarv. Kui arv on 2 või 3, on see selgelt algväärtus ja täiendavaid kontrolle pole vaja.
Aga kui number N on rohkem kui kolm, siis sel juhul läbime kõik võimalikud jagajad, alustades 2-st kuni (N-1). Kui arv N jagub mõne jagajaga ilma jäägita, siis pole see ka algarv. Sel juhul katkestame tsükli (sest edasi pole mõtet kontrollida) ja funktsioon tagastab FALSE.
Pole mõtet kontrollida, kas arv jagub iseendaga (seetõttu kestab tsükkel ainult kuni N-1).
Funktsiooni ennast ma siin ei esita – vaadake seda näidisprogrammidest.
Ülesande 2.30 lahendamine Pascalis minu ülesanne; //**************************************************** **************** //CONSTANTS //******************************** ********* ************************************ COUNT = 100; //Elementide arv massiivis //******************************************** *********** ********************** // FUNKTSIOONID JA PROTSEDUURID //************ ****************************************************** ** //***** ******************************************** * ******* // Kontrollib, kas arv on algarv // SISEND: N - arv // VÄLJUND: TRUE - arv N on algväärtus, VÄÄR - mitte algarv //************ **************************************** **** IsAlgaararv(N: SÕNA) : ; var i: ; algus := TRUE; N 0..3-st: alusta N Välju; lõpp; lõpp; i:= 2 kuni (N-1) tee, kui (N i) = 0, siis //ei alga algarv Tulemus:= VÄÄR; ; lõpp; lõpp; i: WORD; X: SÕNA = 0; A: of WORD; //**************************************************** **************** // PÕHIPROGRAMM //******************************** *************************************** algus //Täitke massiiv numbritega i:= 1 kuni COUNT do A[i] := i; //Loendage ja valige massiivist algarvud jaoks i:= 1 kuni COUNT do if IsPrimeNumber(A[i]), siis algab (X); Write(A[i], " "); lõpp; (#10#13"Aluarvude arv = ", X); WriteLn("Lõpp. Vajutage ENTER..."); ; lõpp.
Ülesande 2.30 lahendus C++ keeles#kaasa
Artiklis käsitletakse alg- ja liitarvude mõisteid. Selliste arvude definitsioonid on toodud näidetega. Esitame tõestuse, et algarvude arv on piiramatu ja märgime selle Eratosthenese meetodil algarvude tabelisse. Esitatakse tõendid, et teha kindlaks, kas arv on alg- või liitarv.
Yandex.RTB R-A-339285-1
Alg- ja liitarvud – definitsioonid ja näited
Alg- ja liitarvud liigitatakse positiivseteks täisarvudeks. Need peavad olema suuremad kui üks. Jagajad jagunevad ka liht- ja liitosadeks. Liitarvude mõiste mõistmiseks peate esmalt uurima jagajate ja kordajate mõisteid.
Definitsioon 1
Algarvud on täisarvud, mis on suuremad kui üks ja millel on kaks positiivset jagajat, st nad ise ja 1.
2. definitsioon
Liitarvud on täisarvud, mis on suuremad kui üks ja millel on vähemalt kolm positiivset jagajat.
Üks ei ole alg- ega liitarv. Sellel on ainult üks positiivne jagaja, seega erineb see kõigist teistest positiivsetest arvudest. Kõiki positiivseid täisarve nimetatakse naturaalarvudeks, see tähendab, et neid kasutatakse loendamisel.
3. definitsioon
algarvud on naturaalarvud, millel on ainult kaks positiivset jagajat.
4. definitsioon
Liitarv- See naturaalarv, millel on rohkem kui kaks positiivset jagajat.
Iga arv, mis on suurem kui 1, on alg- või liitarv. Jaguvuse omadusest saame, et 1 ja arv a jagavad alati mis tahes arvu a, see tähendab, et see jagub enda ja 1-ga. Anname täisarvude definitsiooni.
Definitsioon 5
Naturaalarve, mis ei ole algarvud, nimetatakse liitarvudeks.
Algarvud: 2, 3, 11, 17, 131, 523. Need jaguvad ainult iseenda ja 1-ga. Liitnumbrid: 6, 63, 121, 6697. See tähendab, et arvu 6 saab lagundada 2-ks ja 3-ks ning 63 arvuks 1, 3, 7, 9, 21, 63 ja 121 11-ks, 11-ks, see tähendab, et selle jagajad on 1, 11, 121. Arv 6697 jagatakse 37-ks ja 181-ks. Pange tähele, et algarvude ja koaprarvude mõisted on erinevad mõisted.
Algarvude kasutamise hõlbustamiseks peate kasutama tabelit:
Kõigi olemasolevate naturaalarvude tabel on ebareaalne, kuna neid on lõpmatu arv. Kui arvud jõuavad suuruseni 10000 või 1000000000, peaksite kaaluma Eratosthenese sõela kasutamist.
Vaatleme viimast väidet selgitavat teoreemi.
1. teoreem
Ühest suurema naturaalarvu väikseim positiivne jagaja peale 1 on algarv.
Tõendid 1
Oletame, et a on naturaalarv, mis on suurem kui 1, b on a väikseim mitteühe jagaja. On vaja tõestada, et b on algarv, kasutades vastuolu meetodit.
Oletame, et b on liitarv. Siit saame teada, et b jaoks on jagaja, mis erineb nii 1-st kui ka b-st. Sellist jagajat tähistatakse kui b 1. On vajalik, et tingimus 1< b 1 < b sai valmis.
Tingimusest selgub, et a jagatakse b-ga, b jagatakse b 1-ga, mis tähendab, et jaguvuse mõiste väljendub järgmiselt: a = b q ja b = b 1 · q 1 , kust a = b 1 · (q 1 · q) , kus q ja q 1 on täisarvud. Täisarvude korrutamise reegli kohaselt on täisarvude korrutis täisarv, mille võrdsus on a = b 1 · (q 1 · q) . On näha, et b 1 on arvu a jagaja. Ebavõrdsus 1< b 1 < b Mitte vastab, sest leiame, et b on a väikseim positiivne ja mitte 1 jagaja.
2. teoreem
Algarvusid on lõpmatu arv.
Tõendid 2
Eeldatavasti võtame lõpliku arvu naturaalarve n ja tähistame neid kui p 1, p 2, …, p n. Vaatleme võimalust leida näidatust erinev algarv.
Võtame arvesse arvu p, mis on võrdne p 1, p 2, ..., p n + 1. See ei ole võrdne iga arvuga, mis vastavad algarvudele kujul p 1, p 2, ..., p n. Arv p on algarv. Siis loetakse teoreem tõestatuks. Kui see on liit, peate võtma märge p n + 1 ja näita, et jagaja ei ühti ühegi p 1, p 2, ..., p n-ga.
Kui see nii ei oleks, siis korrutise p 1, p 2, ..., p n jagatavusomaduse põhjal , leiame, et see jagub arvuga pn + 1. Pange tähele, et avaldis p n + 1 arvu p jagamine võrdub summaga p 1, p 2, ..., p n + 1. Saame, et avaldis p n + 1 Selle summa teine liige, mis võrdub 1-ga, tuleb jagada, kuid see on võimatu.
On näha, et antud algarvude hulgast võib leida mis tahes algarvu. Sellest järeldub, et algarve on lõpmatult palju.
Kuna algnumbreid on palju, on tabelid piiratud arvudega 100, 1000, 10000 jne.
Algarvude tabeli koostamisel tuleks arvestada, et selline ülesanne nõuab arvude järjestikust kontrollimist alates 2 kuni 100. Kui jagajat pole, kantakse see tabelisse, kui on liit, siis seda tabelisse ei sisestata.
Vaatame seda samm-sammult.
Kui alustate numbriga 2, on sellel ainult 2 jagajat: 2 ja 1, mis tähendab, et selle saab tabelisse sisestada. Sama numbriga 3. Arv 4 on liit; see tuleb jagada kaheks ja kaheks. Arv 5 on algnumber, mis tähendab, et selle saab tabelisse registreerida. Tehke seda kuni numbrini 100.
See meetod ebamugav ja pikk. Saate luua tabeli, kuid peate kulutama suur hulk aega. Vaja on kasutada jagamiskriteeriume, mis kiirendavad jagajate leidmise protsessi.
Eratosthenese sõela kasutavat meetodit peetakse kõige mugavamaks. Vaatame näitena allolevaid tabeleid. Alustuseks kirjutatakse üles numbrid 2, 3, 4, ..., 50.
Nüüd peate maha kriipsutama kõik arvud, mis on 2-kordsed. Tehke järjestikused läbikriipsud. Saame sellise tabeli:
Jätkame arvude läbikriipsutamisega, mis on 5-kordsed. Saame:
Kriipsutage maha arvud, mis on 7, 11 kordsed. Lõppkokkuvõttes näeb tabel välja selline
Liigume edasi teoreemi sõnastamise juurde.
3. teoreem
Alusarvu a väikseim positiivne ja mitte 1 jagaja ei ületa a, kus a on antud arvu aritmeetiline juur.
Tõendid 3
B on vaja tähistada liitarvu a väikseimat jagajat. On täisarv q, kus a = b · q ja meil on, et b ≤ q. Vormi ebavõrdsus on vastuvõetamatu b > q, sest tingimust rikutakse. Võrratuse b ≤ q mõlemad pooled tuleks korrutada mis tahes positiivse arvuga b, mis ei ole võrdne 1-ga. Saame, et b · b ≤ b · q, kus b 2 ≤ a ja b ≤ a.
Tõestatud teoreemist on selge, et tabelis olevate arvude mahakriipsutamine toob kaasa asjaolu, et on vaja alustada arvuga, mis on võrdne b 2 ja mis rahuldab ebavõrdsust b 2 ≤ a. See tähendab, et kui kriipsutada maha arvud, mis on 2-kordsed, algab protsess 4-ga ja 3-kordsed 9-ga ja nii edasi kuni 100-ni.
Sellise tabeli koostamine Eratosthenese teoreemi abil viitab sellele, et kui kõik liitarvud läbi kriipsutada, jäävad alles algarvud, mis ei ületa n. Näites, kus n = 50, on n = 50. Siit saame, et Eratosthenese sõel sõelub välja kõik liitarvud, mille väärtus ei ole suurem kui 50 juure väärtus. Numbrite otsimine toimub läbi kriipsutades.
Enne lahendamist tuleb välja selgitada, kas arv on alg- või liitarv. Sageli kasutatakse jagamiskriteeriume. Vaatame seda allolevas näites.
Näide 1
Tõesta, et arv 898989898989898989 on liitarv.
Lahendus
Antud arvu numbrite summa on 9 8 + 9 9 = 9 17. See tähendab, et arv 9 · 17 jagub 9-ga jaguvuse testi põhjal 9-ga. Sellest järeldub, et see on liit.
Sellised märgid ei suuda tõestada arvu algväärtust. Kui kontrollimine on vajalik, tuleks võtta muid meetmeid. Sobivaim viis on arvude loendamine. Protsessi käigus saab leida alg- ja liitarve. See tähendab, et arvud ei tohiks ületada väärtust. See tähendab, et arv a tuleb faktoreerida algteguriteks. kui see on täidetud, võib arvu a pidada algarvuks.
Näide 2
Määrake liit- või algarv 11723.
Lahendus
Nüüd peate leidma kõik numbri 11723 jagajad. Vajadus hinnata 11723 .
Siit näeme, et 11723< 200 , то 200 2 = 40 000 ja 11 723< 40 000 . Получаем, что делители для 11 723 меньше числа 200 .
Arvu 11723 täpsemaks hinnanguks peate kirjutama avaldise 108 2 = 11 664 ja 109 2 = 11 881 , See 108 2 < 11 723 < 109 2 . Sellest järeldub, et 11723. a< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.
Laiendades leiame, et 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 on kõik algarvud. Kõik seda protsessi saab kujutada jaotusena veeruga. See tähendab, et jagage 11723 19-ga. Arv 19 on üks selle teguritest, kuna saame jagamise ilma jäägita. Esitame jaotust veeruna:
Sellest järeldub, et 11723 on liitarv, kuna lisaks iseendale ja 1-le on sellel jagaja 19.
Vastus: 11723 on liitarv.
Kui märkate tekstis viga, tõstke see esile ja vajutage Ctrl+Enter
Arvud on erinevad: loomulikud, ratsionaalsed, ratsionaalsed, täis- ja murdarvud, positiivsed ja negatiivsed, keerukad ja algarvud, paaritu ja paaris, tegelik jne. Sellest artiklist saate teada, mis on algarvud.
Milliseid numbreid nimetatakse inglise keeles lihtsateks?
Väga sageli ei tea koolilapsed esmapilgul vastata ühele kõige lihtsamale küsimusele matemaatikas, mis on algarv. Sageli ajavad nad algarvud segi naturaalarvudega (st arvud, mida inimesed kasutavad objektide loendamisel, samas kui mõnes allikas algavad need nulliga ja teistes ühega). Kuid need on täiesti kaks erinevat mõistet. Algarvud on naturaalarvud, st täisarvud ja positiivsed arvud, mis on suuremad kui üks ja millel on ainult 2 loomulik jagaja. Veelgi enam, üks neist jagajatest on antud arv ja teine on üks. Näiteks kolm on algarv, kuna seda ei saa ilma jäägita jagada ühegi teise arvuga peale iseenda ja ühe.
Liitarvud
Algarvude vastand on liitarvud. Nad on ka looduslikud, ka suuremad kui üks, kuid neil pole kaks, vaid suur kogus jagajad. Nii on näiteks arvud 4, 6, 8, 9 jne loomulikud, liitarvud, kuid mitte algarvud. Nagu näete, on need enamasti paarisarvud, kuid mitte kõik. Kuid "kaks" on paarisarv ja "esimene arv" algarvude reas.
Järjekord
Algarvude jada konstrueerimiseks on vaja valida kõigi naturaalarvude hulgast, võttes arvesse nende määratlust, see tähendab, et peate tegutsema vastuoluliselt. Iga positiivset naturaalarvu tuleb uurida, et näha, kas sellel on rohkem kui kaks jagajat. Proovime ehitada jada (jada), mis koosneb algarvudest. Loend algab kahega, millele järgneb kolm, kuna see jagub ainult iseenda ja ühega. Mõelge numbrile neli. Kas sellel on muid jagajaid peale nelja ja ühe? Jah, see arv on 2. Seega neli ei ole algarv. Viis on samuti algarvuga (see ei jagu ühegi teise arvuga, välja arvatud 1 ja 5), kuid kuus on jagatav. Ja üldiselt, kui järgite kõiki paarisarumbreid, märkate, et peale “kahe” pole ükski neist algarvudest. Sellest järeldame, et paarisarvud, välja arvatud kaks, ei ole algarvud. Veel üks avastus: kõik kolmega jaguvad arvud, välja arvatud kolm ise, olgu paaris või paaritud, ei ole samuti algarvud (6, 9, 12, 15, 18, 21, 24, 27 jne). Sama kehtib viie ja seitsmega jaguvate arvude kohta. Ka kogu nende hulk pole lihtne. Teeme kokkuvõtte. Seega sisaldavad lihtsad ühekohalised numbrid kõiki paarituid numbreid, välja arvatud üks ja üheksa, ning isegi "kaks" on paarisarvud. Kümned ise (10, 20,... 40 jne) pole lihtsad. Kahekohalised, kolmekohalised jne algarvud saab määrata ülaltoodud põhimõtete alusel: kui neil pole peale enda ja ühe jagajaid.
Teooriad algarvude omaduste kohta
On olemas teadus, mis uurib täisarvude, sealhulgas algarvude omadusi. See on matemaatika haru, mida nimetatakse kõrgemaks. Lisaks täisarvude omadustele tegeleb ta ka algebraliste ja transtsendentaalsete arvudega ning nende arvude aritmeetikaga seotud erineva päritoluga funktsioonidega. Nendes uuringutes kasutatakse lisaks elementaar- ja algebralistele meetoditele ka analüütilisi ja geomeetrilisi meetodeid. Täpsemalt käsitleb "Arvuteooria" algarvude uurimist.
Algarvud on naturaalarvude "ehituskivid".
Aritmeetikas on teoreem, mida nimetatakse põhiteoreemiks. Selle järgi saab iga naturaalarvu, välja arvatud ühe, esitada korrutisena, mille tegurid on algarvud ja tegurite järjekord on kordumatu, mis tähendab, et esitusviis on kordumatu. Seda nimetatakse naturaalarvu faktoriseerimiseks algteguriteks. Sellel protsessil on ka teine nimi - arvude faktoriseerimine. Selle põhjal võib algarvudeks nimetada " ehitusmaterjal”, “plokid” naturaalarvude konstrueerimiseks.
Otsige algarve. Lihtsuse testid
Paljud eri aegade teadlased püüdsid leida mõningaid põhimõtteid (süsteeme) algarvude loendi leidmiseks. Teadus teab süsteeme, mida nimetatakse Atkini sõelaks, Sundarthami sõelaks ja Eratosthenese sõelaks. Kuid need ei anna olulisi tulemusi ja algarvude leidmiseks kasutatakse lihtsat testi. Matemaatikud lõid ka algoritme. Neid nimetatakse tavaliselt primaalsustestideks. Näiteks on olemas Rabini ja Milleri välja töötatud test. Seda kasutavad krüptograafid. Samuti on olemas Kayal-Agrawal-Sasquena test. Kuid hoolimata piisavast täpsusest on seda väga raske arvutada, mis vähendab selle praktilist tähtsust.
Kas algarvude hulgal on piir?
Vanakreeklane kirjutas oma raamatus “Põhimõtted”, et algarvude hulk on lõpmatus. teadlane Euclid. Ta ütles nii: „Kujutagem korraks ette, et algarvudel on piir. Seejärel korrutame need omavahel ja lisame tootele ühe. Nende lihtsate toimingute tulemusel saadud arvu ei saa jagada ühegi algarvude jadaga, sest jääk jääb alati üheks. See tähendab, et on mõni muu arv, mis ei ole veel algarvude loendis. Seetõttu ei vasta meie oletus tõele ja sellel hulgal ei saa olla piiri. Lisaks Eukleidese tõestusele on olemas ka kaasaegsem valem, mille andis XVIII sajandi Šveitsi matemaatik Leonhard Euler. Selle järgi kasvab esimese n arvu summa pöördsumma arvu n kasvades piiramatult. Ja siin on teoreemi valem algarvude jaotuse kohta: (n) kasvab n/ln (n).
Mis on suurim algarv?
Seesama Leonard Euler suutis leida oma aja suurima algarvu. See on 2 31 - 1 = 2147483647. Aastaks 2013 arvutati aga veel üks kõige täpsem algarvude loendi suurim - 2 57885161 - 1. Seda nimetatakse Mersenne'i arvuks. See sisaldab umbes 17 miljonit kümnendkohta. Nagu näete, on kaheksateistkümnenda sajandi teadlase leitud arv sellest mitu korda väiksem. See oleks pidanud nii olema, sest Euler tegi selle arvutuse käsitsi, samas kui meie kaasaegset aitas ilmselt arvuti. Pealegi saadi see number matemaatikateaduskonnas ühes Ameerika osakonnas. Selle teadlase järgi nimetatud numbrid läbivad Luc-Lemaire'i ürgsuse testi. Teadus ei taha aga sellega peatuda. Electronic Frontier Foundation, mis asutati 1990. aastal Ameerika Ühendriikides (EFF), on pakkunud suurte algarvude leidmise eest rahalist tasu. Ja kui aastani 2013 anti auhind neile teadlastele, kes leiaksid neid 1–10 miljoni hulgast kümnendarvud, siis tänaseks on see arv jõudnud 100 miljonilt 1 miljardile. Auhinnad jäävad vahemikku 150–250 tuhat USA dollarit.
Spetsiaalsete algarvude nimed
Neid numbreid, mis leiti tänu teatud teadlaste loodud algoritmidele ja läbisid lihtsuse testi, nimetatakse erilisteks. Siin on mõned neist:
1. Merssen.
4. Cullen.
6. Mills et al.
Nende ülalnimetatud teadlaste järgi nime saanud numbrite lihtsus tehakse kindlaks järgmiste testide abil:
1. Luc-Lemaire.
2. Pepina.
3. Riisel.
4. Billhart – Lemaire – Selfridge ja teised.
Kaasaegne teadus sellega ei piirdu ja tõenäoliselt saab maailm lähitulevikus teada nende nimed, kes suutsid suurima algarvu leidmisega võita 250 000 dollari suuruse auhinna.
Jagajate loendamine. Definitsiooni järgi arv n on algväärtus ainult siis, kui see ei jagu võrdselt 2-ga ja muude täisarvudega, välja arvatud 1 ja iseendaga. Ülaltoodud valem eemaldab mittevajalikud sammud ja säästab aega: näiteks pärast kontrollimist, kas arv jagub 3-ga, pole vaja kontrollida, kas see jagub 9-ga.
- Funktsioon põranda(x) ümardab x-i lähima täisarvuni, mis on väiksem või võrdne x-ga.
Õppige tundma modulaarset aritmeetikat. Tehe "x mod y" (mod on lühend ladinakeelsest sõnast "modulo", see tähendab "moodul") tähendab "jagage x y-ga ja leidke jääk". Teisisõnu, modulaararitmeetikas teatud väärtuse saavutamisel, mida nimetatakse moodul, numbrid "muutuvad" uuesti nulliks. Näiteks kell hoiab aega mooduliga 12: see näitab kella 10, 11 ja 12 ning seejärel naaseb 1-ni.
- Paljudel kalkulaatoritel on mod-klahv. Selle jaotise lõpus on näidatud, kuidas seda funktsiooni suurte arvude puhul käsitsi hinnata.
Siit saate teada Fermat' väikese teoreemi lõkse. Kõik arvud, mille testitingimused ei ole täidetud, on liitarvud, kuid ülejäänud arvud on ainult ilmselt liigitatakse lihtsateks. Kui soovite vältida valesid tulemusi, otsige n loendis "Carmichaeli numbrid" (liitarvud, mis vastavad sellele testile) ja "pseudoalim-Fermat' numbrid" (need arvud vastavad testitingimustele ainult mõne väärtuse puhul a).
Kui mugav, kasutage Milleri-Rabini testi. Kuigi seda meetodit käsitsi arvutamisel üsna tülikas, kasutatakse seda sageli arvutiprogrammid. See tagab vastuvõetava kiiruse ja tekitab vähem vigu kui Fermat' meetod. Liitarvu ei aktsepteerita algarvuna, kui arvutused tehakse rohkem kui ¼ väärtuste kohta a. Kui valite juhuslikult erinevaid tähendusi a ja test annab neile kõigile positiivne tulemus, võime üsna suure kindlusega eeldada, et n on algarv.
Suurte arvude jaoks kasutage modulaarset aritmeetikat. Kui teil pole käepärast mod-funktsiooniga kalkulaatorit või kalkulaator pole mõeldud selliste toimingutega töötamiseks suured numbrid, kasutage arvutuste hõlbustamiseks astmete omadusi ja moodularitmeetikat. Allpool on näide selle kohta 3 50 (\displaystyle 3^ (50)) mod 50:
- Kirjutage avaldis ümber mugavamal kujul: mod 50. Käsitsi arvutuste tegemisel võib vaja minna täiendavaid lihtsustusi.
- (3 25 ∗ 3 25) (\displaystyle (3^(25)*3^(25))) mod 50 = mod 50 mod 50) mod 50. Siin võtsime arvesse modulaarse korrutamise omadust.
- 3 25 (\displaystyle 3^(25)) mod 50 = 43.
- (3 25 (\displaystyle (3^(25)) mood 50 ∗ 3 25 (\displaystyle *3^(25)) mod 50) mod 50 = (43 * 43) (\displaystyle (43*43)) mood 50.
- = 1849 (\displaystyle =1849) mood 50.
- = 49 (\displaystyle =49).
Selles artiklis uurime alg- ja liitarvud. Esiteks anname alg- ja liitarvude määratlused ning toome ka näiteid. Pärast seda tõestame, et algarve on lõpmatult palju. Järgmisena kirjutame üles algarvude tabeli ja kaalume algarvude tabeli koostamise meetodeid, pöörates erilist tähelepanu meetodile, mida nimetatakse Eratosthenese sõelaks. Kokkuvõtteks toome välja peamised punktid, mida tuleb arvestada, kui tõestada, et antud arv on alg- või liitarv.
Leheküljel navigeerimine.
Alg- ja liitarvud – definitsioonid ja näited
Algarvude ja liitarvude mõisted viitavad arvudele, mis on suuremad kui üks. Sellised täisarvud jagatakse sõltuvalt nende positiivsete jagajate arvust alg- ja liitarvudeks. Nii et aru saada alg- ja liitarvude määratlused, peate hästi aru saama, mis on jagajad ja kordsed.
Definitsioon.
algarvud on täisarvud, suured ühikud, millel on ainult kaks positiivset jagajat, nimelt nad ise ja 1.
Definitsioon.
Liitarvud on täisarvud, suured, millel on vähemalt kolm positiivset jagajat.
Eraldi märgime, et arv 1 ei kehti ei alg- ega liitarvude kohta. Ühikul on ainult üks positiivne jagaja, milleks on arv 1 ise. See eristab arvu 1 kõigist teistest positiivsetest täisarvudest, millel on vähemalt kaks positiivset jagajat.
Arvestades, et positiivsed täisarvud on , ja ühel on ainult üks positiivne jagaja, saame alg- ja liitarvude esitatud definitsioonidest anda teisi formulatsioone.
Definitsioon.
algarvud on naturaalarvud, millel on ainult kaks positiivset jagajat.
Definitsioon.
Liitarvud on naturaalarvud, millel on rohkem kui kaks positiivset jagajat.
Pange tähele, et iga ühest suurem positiivne täisarv on kas alg- või liitarv. Teisisõnu, pole ühtegi täisarvu, mis ei oleks alg- ega liitarvu. See tuleneb jaguvuse omadusest, mis väidab, et arvud 1 ja a on alati mis tahes täisarvu a jagajad.
Eelmises lõigus toodud teabe põhjal saame anda liitarvude järgmise definitsiooni.
Definitsioon.
Nimetatakse naturaalarvusid, mis ei ole algarvud komposiit.
Anname näiteid alg- ja liitarvudest.
Liitarvude näited on 6, 63, 121 ja 6697. Ka see väide vajab täpsustamist. Arv 6 sisaldab lisaks positiivsetele jagajatele 1 ja 6 ka jagajaid 2 ja 3, kuna 6 = 2 3, seega on 6 tõesti liitarv. Positiivsed tegurid 63 on numbrid 1, 3, 7, 9, 21 ja 63. Arv 121 võrdub korrutisega 11·11, seega on selle positiivsed jagajad 1, 11 ja 121. Ja arv 6697 on liit, kuna selle positiivsed jagajad on lisaks numbritele 1 ja 6697 ka numbrid 37 ja 181.
Selle punkti lõpetuseks tahaksin juhtida tähelepanu ka asjaolule, et algarvud ja koaprarvud pole kaugeltki samad.
Algarvude tabel
Algarvud, mugavuse huvides edasine kasutamine, salvestatakse tabelisse, mida nimetatakse algarvude tabeliks. Allpool on algarvude tabel kuni 1000.
Tekib loogiline küsimus: "Miks me täitsime algarvude tabeli ainult kuni 1000-ni, kas pole võimalik teha tabelit kõigist olemasolevatest algarvudest"?
Vastame kõigepealt selle küsimuse esimesele osale. Enamiku probleemide puhul, mis nõuavad algarvude kasutamist, piisab tuhande piires olevatest algarvudest. Muudel juhtudel peate tõenäoliselt kasutama mõnda erilahendust. Kuigi me saame kindlasti luua algarvude tabeli kuni suvaliselt suure lõpliku positiivse täisarvuni, olgu selleks siis 10 000 või 1 000 000 000, räägime järgmises lõigus algarvude tabelite loomise meetoditest, eelkõige vaatleme meetodit. helistas.
Nüüd vaatame võimalust (õigemini võimatust) koostada tabel kõigist olemasolevatest algarvudest. Me ei saa koostada tabelit kõigist algarvudest, sest algarve on lõpmatult palju. Viimane väide on teoreem, mida me tõestame pärast järgmist abiteoreemi.
Teoreem.
Ühest suurema naturaalarvu väikseim positiivne jagaja peale 1 on algarv.
Tõestus.
Lase a on naturaalarv, mis on suurem kui üks, ja b on väikseim positiivne jagaja, mis ei ole üks. Tõestame vastuoluga, et b on algarv.
Oletame, et b on liitarv. Siis on arvu b jagaja (tähistame selle b 1), mis erineb nii arvust 1 kui ka b. Kui arvestada ka seda, et jagaja absoluutväärtus ei ületa dividendi absoluutväärtust (seda teame jaguvuse omaduste järgi), siis peab tingimus 1 olema täidetud
Kuna arv a jagub tingimuse järgi b-ga ja me ütlesime, et b jagub b 1-ga, võimaldab jaguvuse mõiste rääkida täisarvude q ja q 1 olemasolust nii, et a=b q ja b=b 1 q 1, kust a= b 1 · (q 1 · q) . Sellest järeldub, et kahe täisarvu korrutis on täisarv, siis võrdus a=b 1 ·(q 1 ·q) näitab, et b 1 on arvu a jagaja. Võttes arvesse ülaltoodud ebavõrdsust 1
Nüüd saame tõestada, et algarve on lõpmatult palju.
Teoreem.
Algarvusid on lõpmatu arv.
Tõestus.
Oletame, et see pole nii. See tähendab, et oletame, et on ainult n algarvu ja need algarvud on p 1, p 2, ..., p n. Näitame, et me võime alati leida näidatust erineva algarvu.
Vaatleme arvu p, mis on võrdne p 1 · p 2 ·… · p n +1. On selge, et see arv erineb igast algarvust p 1, p 2, ..., p n. Kui arv p on algarvuga, siis on teoreem tõestatud. Kui see arv on liitarv, siis eelneva teoreemi kohaselt on sellel arvul algjagaja (tähistame p n+1). Näitame, et see jagaja ei lange kokku ühegi arvuga p 1, p 2, ..., p n.
Kui see nii ei oleks, jagataks korrutis p 1 ·p 2 ·…·p n vastavalt jaguvuse omadustele p n+1-ga. Kuid arv p jagub ka arvuga p n+1, mis on võrdne summaga p 1 ·p 2 ·…·p n +1. Sellest järeldub, et p n+1 peab jagama selle summa teise liikme, mis on võrdne ühega, kuid see on võimatu.
Seega on tõestatud, et alati võib leida uue algarvu, mis ei kuulu ühegi ettemääratud algarvu hulka. Seetõttu on algarve lõpmatult palju.
Seega, kuna algarvusid on lõpmatult palju, siis algarvude tabeleid koostades piirdute alati ülalt mõne arvuga, tavaliselt 100, 1000, 10 000 jne.
Eratosthenese sõel
Nüüd käsitleme algarvude tabelite loomise viise. Oletame, et peame koostama tabeli algarvudest kuni 100.
Kõige ilmsem meetod selle ülesande lahendamiseks on järjestikuste positiivsete täisarvude kontrollimine alates 2-st ja lõpetades 100-ga positiivse jagaja olemasolu suhtes, mis on suurem kui 1 ja väiksem kui testitav arv (meile teadaolevate jaguvuse omaduste põhjal et jagaja absoluutväärtus ei ületaks dividendi absoluutväärtust, nullist erinev). Kui sellist jagajat ei leita, on testitav arv algarvu ja see sisestatakse algarvude tabelisse. Kui selline jagaja leitakse, siis on testitav arv liitarv, seda EI sisestata algarvude tabelisse. Pärast seda toimub üleminek järgmisele numbrile, mida samamoodi kontrollitakse jagaja olemasolu suhtes.
Kirjeldame paar esimest sammu.
Alustame numbriga 2. Arvul 2 pole peale 1 ja 2 positiivseid jagajaid. Seetõttu on see lihtne, seetõttu sisestame selle algarvude tabelisse. Siin tuleks öelda, et 2 on väikseim algarv. Liigume edasi numbri 3 juurde. Selle võimalik positiivne jagaja peale 1 ja 3 on arv 2. Kuid 3 ei jagu 2-ga, seetõttu on 3 algarv ja see tuleb lisada ka algarvude tabelisse. Liigume edasi numbri 4 juurde. Selle positiivsed jagajad peale 1 ja 4 võivad olla numbrid 2 ja 3, kontrollime neid. Arv 4 jagub 2-ga, seetõttu on 4 liitarv ja seda ei pea algarvude tabelisse kaasama. Pange tähele, et 4 on väikseim liitarv. Liigume edasi numbri 5 juurde. Kontrollime, kas vähemalt üks arvudest 2, 3, 4 on selle jagaja. Kuna 5 ei jagu 2, 3 ega 4-ga, siis on see algarv ja see tuleb algarvude tabelisse üles kirjutada. Seejärel toimub üleminek numbritele 6, 7 ja nii edasi kuni 100-ni.
Selline lähenemine algarvude tabeli koostamisel ei ole kaugeltki ideaalne. Nii või teisiti on tal õigus eksisteerida. Pange tähele, et selle täisarvude tabeli koostamise meetodi puhul saate kasutada jagamiskriteeriume, mis kiirendavad pisut jagajate leidmist.
Algarvude tabeli loomiseks on mugavam viis, nn. Nimes sisalduv sõna “sõel” pole juhuslik, kuna selle meetodi toimingud aitavad justkui täisarve ja suuri ühikuid läbi Eratosthenese sõela “sõeluda”, et eraldada lihtsad liitarvudest.
Näitame Eratosthenese sõela töös algarvude kuni 50 tabeli koostamisel.
Kõigepealt kirjutage järjekorras numbrid 2, 3, 4, ..., 50.
Esimene kirjutatud arv 2 on algarv. Nüüd, numbrist 2, liigume järjestikku kahe numbri võrra paremale ja kriipsutame need arvud maha, kuni jõuame koostatava arvutabeli lõppu. See kriipsutab läbi kõik arvud, mis on kahe kordsed.
Esimene number 2-le järgnev, mida läbi ei kriipsutata, on 3. See arv on algarv. Nüüd, numbrist 3, liigume järjestikku kolme numbri võrra paremale (arvestades juba läbikriipsutatud numbreid) ja kriipsutame need maha. See kriipsutab läbi kõik arvud, mis on kolme kordsed.
Esimene number pärast 3, mis ei ole läbi kriipsutatud, on 5. See arv on algarv. Nüüd liigume numbrist 5 järjekindlalt 5 numbri võrra paremale (arvestame ka varem läbikriipsutatud numbreid) ja kriipsutame need maha. See kriipsutab välja kõik arvud, mis on viie kordsed.
Järgmisena kriipsutame maha arvud, mis on 7-kordsed, seejärel 11-kordsed ja nii edasi. Protsess lõpeb, kui maha kriipsutada pole enam numbreid. Allpool on täidetud tabel algarvudest kuni 50, mis on saadud Eratosthenese sõela abil. Kõik ristimata arvud on algarvud ja kõik läbikriipsutatud arvud on liitarvud.
Sõnastame ja tõestame ka teoreemi, mis kiirendab Eratosthenese sõela abil algarvude tabeli koostamist.
Teoreem.
Ühest erineva liitarvu a väikseim positiivne jagaja ei ületa , kus on a .
Tõestus.
Tähistame tähega b liitarvu a väikseimat jagajat, mis erineb ühest (arv b on algarvuga, nagu tuleneb päris eelmise lõigu alguses tõestatud teoreemist). Siis on täisarv q nii, et a=b·q (siin q on positiivne täisarv, mis tuleneb täisarvude korrutamise reeglitest) ja (b>q puhul on rikutud tingimus, et b on a vähim jagaja , kuna q on ka arvu a jagaja võrrandi a=q·b tõttu). Korrutades mõlemad pooled ebavõrdsus positiivse ja täisarv suurem kui üks (meil on lubatud seda teha), saame , Millest ja .
Mida annab meile tõestatud teoreem Eratosthenese sõela kohta?
Esiteks peaks algarvu b kordsete liitarvude mahakriipsutamine algama arvuga, mis on võrdne (see tuleneb ebavõrdsusest). Näiteks kahe kordsete arvude mahakriipsutamine peaks algama numbriga 4, kolmekordsed arvuga 9, viiekordsed arvuga 25 jne.
Teiseks võib Eratosthenese sõela abil algarvude tabeli koostamist kuni arvuni n lugeda lõpetatuks, kui kõik liitarvud, mis on algarvude kordsed, ei ületa . Meie näites n=50 (kuna me koostame algarvude tabelit kuni 50) ja seetõttu peaks Eratosthenese sõel kõrvaldama kõik liitarvud, mis on algarvude 2, 3, 5 ja 7 kordsed. ei ületa aritmeetilist ruutjuurt 50. See tähendab, et me ei pea enam otsima ja läbi kriipsutama arve, mis on algarvude 11, 13, 17, 19, 23 kordsed ja nii edasi kuni 47-ni, kuna need kriipsutatakse juba läbi väiksemate algarvude 2 kordajatena. , 3, 5 ja 7 .
Kas see arv on alg- või liitarv?
Mõned ülesanded nõuavad välja selgitamist, kas antud arv on alg- või liitarv. Üldiselt pole see ülesanne kaugeltki lihtne, eriti numbrite puhul, mille kirjutamine koosneb märkimisväärsest arvust tähemärkidest. Enamasti tuleb selle lahendamiseks otsida mingi konkreetne viis. Mõttekäigule püüame aga suuna anda lihtsate juhtumite puhul.
Muidugi võite proovida kasutada jaguvustesti, et tõestada, et antud arv on liitarv. Kui näiteks mõni jaguvuse test näitab, et antud arv jagub mõne positiivse täisarvuga, mis on suurem kui üks, siis on esialgne arv liitarv.
Näide.
Tõesta, et 898 989 898 989 898 989 on liitarv.
Lahendus.
Selle arvu numbrite summa on 9·8+9·9=9·17. Kuna 9·17-ga võrdne arv jagub 9-ga, siis jaguvuse 9-ga saame öelda, et ka algne arv jagub 9-ga. Seetõttu on see komposiit.
Selle lähenemisviisi oluliseks puuduseks on see, et jaguvuse kriteeriumid ei võimalda tõestada arvu algväärtust. Seega, kui testite arvu, et näha, kas see on alg- või liitarvu, peate toimima teisiti.
Kõige loogilisem lähenemine on proovida antud arvu kõiki võimalikke jagajaid. Kui ükski võimalikest jagajatest ei ole antud arvu tegelik jagaja, on see arv algarvuks, vastasel juhul on see liitarv. Eelmises lõigus tõestatud teoreemidest järeldub, et antud arvu a jagajaid tuleb otsida algarvude hulgast, mis ei ületa . Seega saab antud arvu a järjestikku jagada algarvudega (mis on mugavalt võetud algarvude tabelist), püüdes leida arvu a jagajat. Kui jagaja leitakse, on arv a liit. Kui algarvude hulgas, mis ei ületa , ei ole arvu a jagajat, siis on arv a algarvu.
Näide.
Number 11 723 lihtne või liit?
Lahendus.
Uurime, millise algarvuni võivad olla arvu 11 723 jagajad. Selleks hindame.
See on üsna ilmne 
, alates 200 2 = 40 000 ja 11 723<40 000
(при необходимости смотрите статью numbrite võrdlus). Seega on 11 723 võimalikud algtegurid väiksemad kui 200. See muudab meie ülesande juba palju lihtsamaks. Kui me seda ei teaks, peaksime läbima kõik algarvud mitte kuni 200-ni, vaid kuni arvuni 11 723.
Soovi korral saab täpsemalt hinnata. Kuna 108 2 = 11 664 ja 109 2 = 11 881, siis 108 2<11 723<109 2
, следовательно, 
. Seega kõik algarvud, mis on väiksemad kui 109, on potentsiaalselt antud arvu 11 723 algtegur.
Nüüd jagame arvu 11 723 järjestikku algarvudeks 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 . Kui arv 11 723 jagatakse ühe kirjutatud algarvuga, on see liit. Kui see ei jagu ühegi kirjutatud algarvuga, on algarv algarv.
Me ei kirjelda kogu seda monotoonset ja monotoonset jagunemisprotsessi. Ütleme kohe, et 11 723