Pirminių skaičių generatorius internetu

Kas yra pirminis skaičius?

Pirminis skaičius yra natūralusis skaičius, didesnis už 1, kuris dalijasi tik iš vieneto ir pats iš savęs. Mažiausi pirminiai skaičiai yra 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… Skaičius 2 yra vienintelis lyginis pirminis skaičius – visi kiti lyginiai skaičiai dalijasi iš dviejų.

Skaičiai, tokie kaip 4 (= 2 × 2), 6 (= 2 × 3) arba 15 (= 3 × 5), nėra pirminiai – jie vadinami sudėtiniais skaičiais.

Kaip veikia generatorius?

Norėdami išvardyti visus pirminius skaičius diapazone, naudojame Eratosteno rėtį – vieną seniausių ir efektyviausių algoritmų, kurį apie 240 m. pr. Kr. aprašė graikų matematikas Eratostenas iš Kirėnės.

Algoritmas palaipsniui išbraukia kiekvieno rastojo pirminio skaičiaus kartotinius. Kas lieka, yra pirminiai skaičiai. Visas skaičiavimas atliekamas tiesiogiai jūsų naršyklėje – jokie duomenys nesiunčiami į serverį.

Atsitiktiniam pasirinkimui generatorius pirmiausia sudaro visų pirminių skaičių diapazone sąrašą, o tada atsitiktinai pasirenka norimą skaičių naudodamas kriptografiškai saugų generatorių (crypto.getRandomValues()).

Generatoriaus funkcijos

• Visi pirminiai skaičiai – išvardija kiekvieną pirminį skaičių nurodytame diapazone (maks. 10 000)
• Atsitiktinis pasirinkimas – pasirenka N atsitiktinių pirminių skaičių iš diapazono (tinka dideliems diapazonams)
• Rūšiavimas – rūšiuoti rezultatus didėjimo tvarka
• Skyriklis – pasirinkite, kaip skaičiai bus atskirti kopijuojant
• Greiti nustatymai – dažniausiai naudojami diapazonai vienu paspaudimu

Kur naudojami pirminiai skaičiai?

Kriptografija ir saugumas

Pirminiai skaičiai yra moderniosios kriptografijos pagrindas. Algoritmai, tokie kaip RSA, veikia principu, kad dviejų didelių pirminių skaičių sandaugą lengva apskaičiuoti, tačiau atgalinis išskaidymas į pirminius dauginamuosius yra skaičiavimo prasme labai sudėtingas.

• RSA šifravimas – raktai generuojami iš dviejų didelių pirminių skaičių
• Diffie-Hellman – raktų keitimas naudojant pirminį modulį
• Maišos funkcijos – pirminiai skaičiai kaip maginės konstantos (SHA, MD5)

Matematika ir mokslas

• Skaičių teorija – pagrindiniai sveikųjų skaičių statybiniai blokai
• Goldbacho spėjimas – kiekvienas lyginis skaičius > 2 gali būti išreikštas kaip dviejų pirminių skaičių suma (dar neįrodyta)
• Riemanno hipotezė – viena iš Hilberto problemų, susijusi su pirminių skaičių pasiskirstymu

Praktinis pritaikymas

• Maišos lentelės – lentelės dydis kaip pirminis skaičius sumažina kolizijas
• Pseudonaują atsitiktinių skaičių generatoriai – tiesinė kongruencija su pirminiu moduliu
• Muzika ir ritmas – poliritmai su pirminiais ciklo ilgiais

Pirminių skaičių pasiskirstymas

Pirminiai skaičiai natūraliųjų skaičių sekoje pasiskirstę nereguliariai, tačiau jų tankis mažėja didėjant diapazonui. Tai aprašo Pirminių skaičių teorema: pirminių skaičių skaičius iki N yra apytiksliai N / ln(N).

Eratosteno rėtis žingsnis po žingsnio

Diapazonas 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. Pasirinkite 2, išbraukite kartotinius: 4, 6, 8, 10, 12...
2. Pasirinkite 3, išbraukite kartotinius: 9, 15, 21, 27...
3. Pasirinkite 5, išbraukite kartotinius: 25...
4. √30 ≈ 5.5 → atlikta

Pirminiai skaičiai: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Eratosteno rėtis kode

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

Dažnai užduodami klausimai (DUK)