Pirminis skaičius
Pirminis skaičius – bet kuris natūralusis skaičius, didesnis nei 1, kuris dalinasi tik iš savęs ir vieneto. Vienetas nelaikomas nei pirminiu skaičiumi, nei sudėtiniu.
Keletas mažiausių pirminių skaičių:
- 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, 109, 113, …
Pirminių skaičių yra be galo daug.
2017 metų gruodį GIMPS (ang. Great Internet Mersenne Prime Search) projekto pagalba surastas kol kas didžiausias (23,249,425 skaitmenų ilgio) pirminis skaičius . Tai taip pat yra didžiausias žinomas Merseno skaičius.
Eratosteno rėtis[redaguoti | redaguoti vikitekstą]
Graikų matematikas Eratostenas dar II a. pr. m. e. pasiūlė paprastą metodą kaip rasti visus pirminius skaičius nuo 2 iki n. Metodas labai paprastas – reikia surašyti visus skaičius nuo 2 iki n ir pradurti sudėtinius skaičius. Tokiu būdu lieka 'rėtis', kuriame liko tik pirminiai skaičiai.
Pradūrimas vyksta taip: iš pradžių niekas nėra pradurta. Pradedant nuo 2, ieškome nepradurto skaičiaus – randame 2. Tada praduriame visus dvejeto kartotinius. Vėl ieškome pirmo nepradurto skaičiaus – randame 3. Praduriame visus trejeto kartotinius. Dabar ieškodami jau randame 5, nes 4 yra pradurtas.[1]
Merseno skaičiai[redaguoti | redaguoti vikitekstą]
Žymus prancūzų fizikas ir mokslo populiarintojas M. Mersenas (1588–1648) pastebėjo, kad daugelio pirminių skaičių pavidalas yra 2p-1 (p – pirminis skaičius).
Visi tokio pavidalo skaičiai vadinami Merseno skaičiais. Tačiau ne visi Merseno skaičiai yra pirminiai.[1]
Šaltiniai[redaguoti | redaguoti vikitekstą]
- ↑ 1,0 1,1 V. Dagienė, G. Grigas, K. Augutis. Šimtas programavimo uždavinių. Šviesa, 1986. 223 p.