Primskaitļu ģenerators tiešsaistē

Kas ir pirmskaitlis?

Pirmskaitlis ir dabisks skaitlis, kas lielāks par 1 un ir dalāms tikai ar 1 un sevi pašu. Mazākie pirmskaitļi ir 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… Skaitlis 2 ir vienīgais pāra pirmskaitlis – visi pārējie pāra skaitļi ir dalāmi ar divi.

Skaitļi, piemēram, 4 (= 2 × 2), 6 (= 2 × 3) vai 15 (= 3 × 5), nav pirmskaitļi – tos sauc par saliktiem skaitļiem.

Kā darbojas ģenerators?

Lai uzskaitītu visus pirmskaitļus diapazonā, mēs izmantojam Eratostena sietu – vienu no senākajiem un efektīvākajiem algoritmiem, ko aprakstīja grieķu matemātiķis Eratostens no Kirēnas ap 240. gadu p.m.ē.

Algoritms pakāpeniski izsvītro katra atrastā pirmskaitļa reizinājumus. Atlikušie ir pirmskaitļi. Visi aprēķini notiek tieši jūsu pārlūkprogrammā – nekādi dati netiek sūtīti uz serveri.

Nejaušai izlasei ģenerators vispirms sastāda visu pirmskaitļu sarakstu diapazonā un pēc tam no tā nejauši izvēlas nepieciešamo skaitu, izmantojot kriptogrāfiski drošu ģeneratoru (crypto.getRandomValues()).

Ģeneratora funkcijas

• Visi pirmskaitļi – uzskaita katru pirmskaitli dotajā diapazonā (maks. 10 000)
• Nejauša izlase – izvēlas N nejaušus pirmskaitļus no diapazona (piemērots lieliem diapazoniem)
• Kārtošana – kārtojiet rezultātus augošā secībā
• Atdalītājs – izvēlieties, kā skaitļi tiks atdalīti, kopējot
• Ātrie iestatījumi – visbiežāk izmantotie diapazoni ar vienu klikšķi

Kur tiek izmantoti pirmskaitļi?

Kriptogrāfija un drošība

Pirmskaitļi ir mūsdienu kriptogrāfijas pamatā. Algoritmi, piemēram, RSA, darbojas pēc principa, ka divu lielu pirmskaitļu reizinājumu ir viegli aprēķināt, bet atpakaļejoša sadalīšana pirmskaitļu reizinātājos ir skaitļošanas ziņā ļoti sarežģīta.

• RSA šifrēšana – atslēgas tiek ģenerētas no diviem lieliem pirmskaitļiem
• Diffie-Hellman – atslēgu apmaiņa virs pirmskaitļa moduļa
• Jaukšanas funkcijas – pirmskaitļi kā maģiskas konstantes (SHA, MD5)

Matemātika un zinātne

• Skaitļu teorija – veselo skaitļu pamatbloki
• Goldbaha hipotēze – katru pāra skaitli > 2 var izteikt kā divu pirmskaitļu summu (vēl nav pierādīta)
• Rīmaņa hipotēze – viena no Hilberta problēmām, attiecas uz pirmskaitļu sadalījumu

Praktiskais pielietojums

• Jauktabulas – tabulas lielums kā pirmskaitlis samazina kolīzijas
• Pseidonejaušo skaitļu ģeneratori – lineāra kongruence ar pirmskaitļa moduli
• Mūzika un ritms – poliritmi ar pirmskaitļu ciklu garumiem

Pirmskaitļu sadalījums

Pirmskaitļi starp dabiskajiem skaitļiem ir izvietoti neregulāri, bet to blīvums samazinās, palielinoties diapazonam. To apraksta Pirmskaitļu teorēma: pirmskaitļu skaits līdz N ir aptuveni N / ln(N).

Eratostena siets soli pa solim

Diapazons 2–30:
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]

1. Izvēlies 2, izsvītro reizinājumus: 4, 6, 8, 10, 12...
2. Izvēlies 3, izsvītro reizinājumus: 9, 15, 21, 27...
3. Izvēlies 5, izsvītro reizinājumus: 25...
4. √30 ≈ 5.5 → pabeigts

Pirmskaitļi: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Eratostena siets kodā

JavaScript

function sieve(to) {
  const composite = new Uint8Array(to + 1);
  const primes = [];
  for (let p = 2; p <= to; p++) {
    if (composite[p]) continue;
    primes.push(p);
    for (let j = p * p; j <= to; j += p) composite[j] = 1;
  }
  return primes;
}

Python

def sieve(n):
    composite = bytearray(n + 1)
    primes = []
    for p in range(2, n + 1):
        if not composite[p]:
            primes.append(p)
            for j in range(p * p, n + 1, p):
                composite[j] = 1
    return primes

Biežāk uzdotie jautājumi (BUJ)