Pirminis skaičius

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

Pirminis skaičius yra 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. Didžiausias žinomas pirminis skaičius iki 2008 m. rugsėjo buvo 2^32582657 − 1. Jis buvo rastas 2006 m. rugsėjo 6 d. Tai yra 44-as Merseno skaičius. 2008 metais rugsėjo mėnesį Kalifornijos matematikai rado naują didžiausią, 13 mln. skaitmenų ilgio pirminį skaičių (2^{43 112 609} − 1, taip pat Merseno skaičius).

[taisyti] Eratosteno rėtis

Pagrindinis straipsnis: Eratosteno rėtis

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. Tokius 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.

[taisyti] Merseno skaičiai

Pagrindinis straipsnis: Merseno skaičiai

Žymus prancūzų fizikas ir mokslo populiarintojas M. Mersenas (1588-1648) pastebėjo, kad daugelio pirminių skaičių pavidalas yra 2^p-1 (p – pirminis skaičius).
Visi tokio pavidalo skaičiai vadinami Merseno skaičiais. Tačiau ne visi Merseno skaičiai yra pirminiai.