# Pirminių skaičių generatorius

> Greitai generuokite pirminius skaičius nurodytame diapazone arba atsitiktinai. Naudoja Eratosteno rėtį naršyklėje – be serverio, nemokamai.

URL: https://acrafto.com/lt/pirminiu-skaiciu-generatorius/

Tools are interactive browser apps; there is no public API, no endpoints to call and no server-side processing. To use a tool, open its HTML page in a browser.

## 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).

| Diapazonas | Pirminių skaičių skaičius |
| --- | --- |
| 1–10 | 4 |
| 1–100 | 25 |
| 1–1 000 | 168 |
| 1–10 000 | 1 229 |
| 1–100 000 | 9 592 |
| 1–1 000 000 | 78 498 |

## 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)

### Ar 1 yra pirminis skaičius?

Ne. Skaičius 1 tradiciškai nelaikomas pirminiu skaičiumi. Priežastis yra matematinė – jei 1 laikytume pirminiu skaičiumi, vienareikšmiškumo teorema apie išskaidymą pirminiais dauginamaisiais prarastų galią.

### Ar 2 yra pirminis skaičius?

Taip. Skaičius 2 yra mažiausias ir vienintelis lyginis pirminis skaičius. Visi kiti lyginiai skaičiai dalijasi iš dviejų, todėl yra sudėtiniai.

### Kiek yra pirminių skaičių?

Begalybė. Euklidas tai įrodė apie 300 m. pr. Kr. elegantišku prieštaros būdu: tarkime, kad yra baigtinis pirminių skaičių skaičius. Jų sandauga + 1 negalėtų būti dalijama iš nė vieno iš jų – vadinasi, tai yra naujas pirminis skaičius, prieštara.

### Kas yra pirminių skaičių dvyniai?

Pirminių skaičių dvyniai yra pirminių skaičių poros, besiskiriančios 2, pavyzdžiui, (3, 5), (11, 13), (17, 19), (41, 43). Ar jų yra be galo daug, iki šiol yra neišspręstas matematikos klausimas (Pirminių skaičių dvynių spėjimas).

### Kaip greitai veikia algoritmas?

Eratosteno rėčio laiko sudėtingumas yra O(n log log n). Diapazonui iki 10 milijonų skaičiavimas naršyklėje paprastai trunka mažiau nei 100 ms.

## Other languages

- Čeština (cs): [Generátor prvočísel](https://acrafto.com/cs/generator-prvocisel/) ([Markdown](https://acrafto.com/cs/generator-prvocisel/index.md))
- Slovenčina (sk): [Generátor prvočísel](https://acrafto.com/sk/generator-prvocisel/) ([Markdown](https://acrafto.com/sk/generator-prvocisel/index.md))
- English (en): [Prime Number Generator](https://acrafto.com/en/prime-number-generator/) ([Markdown](https://acrafto.com/en/prime-number-generator/index.md))
- Deutsch (de): [Primzahlgenerator](https://acrafto.com/de/online-primzahl-generator/) ([Markdown](https://acrafto.com/de/online-primzahl-generator/index.md))
- Français (fr): [Générateur de nombres premiers](https://acrafto.com/fr/generateur-nombres-premiers/) ([Markdown](https://acrafto.com/fr/generateur-nombres-premiers/index.md))
- Español (es): [Generador de números primos](https://acrafto.com/es/generador-numeros-primos-online/) ([Markdown](https://acrafto.com/es/generador-numeros-primos-online/index.md))
- Italiano (it): [Generatore di numeri primi](https://acrafto.com/it/generatore-numeri-primi/) ([Markdown](https://acrafto.com/it/generatore-numeri-primi/index.md))
- Português (pt): [Gerador de números primos](https://acrafto.com/pt/gerador-numeros-primos-online/) ([Markdown](https://acrafto.com/pt/gerador-numeros-primos-online/index.md))
- Nederlands (nl): [Priemgetallengenerator](https://acrafto.com/nl/online-priemgetalgenerator/) ([Markdown](https://acrafto.com/nl/online-priemgetalgenerator/index.md))
- Polski (pl): [Generator liczb pierwszych](https://acrafto.com/pl/generator-liczb-pierwszych/) ([Markdown](https://acrafto.com/pl/generator-liczb-pierwszych/index.md))
- Română (ro): [Generator numere prime](https://acrafto.com/ro/generator-numere-prime-online/) ([Markdown](https://acrafto.com/ro/generator-numere-prime-online/index.md))
- Magyar (hu): [Prímszám generátor](https://acrafto.com/hu/primszam-generator/) ([Markdown](https://acrafto.com/hu/primszam-generator/index.md))
- Ελληνικά (el): [Γεννήτρια πρώτων αριθμών](https://acrafto.com/el/gennitria-proton-arithmon-online/) ([Markdown](https://acrafto.com/el/gennitria-proton-arithmon-online/index.md))
- Български (bg): [Генератор на прости числа](https://acrafto.com/bg/generator-na-prosti-chisla-onlajn/) ([Markdown](https://acrafto.com/bg/generator-na-prosti-chisla-onlajn/index.md))
- Hrvatski (hr): [Generator prostih brojeva](https://acrafto.com/hr/generator-prostih-brojeva-online/) ([Markdown](https://acrafto.com/hr/generator-prostih-brojeva-online/index.md))
- Slovenščina (sl): [Generator praštevil](https://acrafto.com/sl/generator-prastevil/) ([Markdown](https://acrafto.com/sl/generator-prastevil/index.md))
- Eesti (et): [Algarvude generaator](https://acrafto.com/et/algarvude-generaator/) ([Markdown](https://acrafto.com/et/algarvude-generaator/index.md))
- Latviešu (lv): [Pirmskaitļu ģenerators](https://acrafto.com/lv/primskaitlu-generators/) ([Markdown](https://acrafto.com/lv/primskaitlu-generators/index.md))
- Svenska (sv): [Primtalsgenerator](https://acrafto.com/sv/primtalsgenerator-online/) ([Markdown](https://acrafto.com/sv/primtalsgenerator-online/index.md))
- Dansk (da): [Primtalsgenerator](https://acrafto.com/da/primtal-generator-online/) ([Markdown](https://acrafto.com/da/primtal-generator-online/index.md))
- Suomi (fi): [Alkulukugeneraattori](https://acrafto.com/fi/alkuluku-generaattori/) ([Markdown](https://acrafto.com/fi/alkuluku-generaattori/index.md))
- Norsk (no): [Primtallsgenerator](https://acrafto.com/no/primtallsgenerator/) ([Markdown](https://acrafto.com/no/primtallsgenerator/index.md))
- Українська (uk): [Генератор простих чисел](https://acrafto.com/uk/generator-prostyh-chysel/) ([Markdown](https://acrafto.com/uk/generator-prostyh-chysel/index.md))
- Русский (ru): [Генератор простых чисел](https://acrafto.com/ru/generator-prostykh-chisel-onlayn/) ([Markdown](https://acrafto.com/ru/generator-prostykh-chisel-onlayn/index.md))
- Српски (sr): [Generator prostih brojeva](https://acrafto.com/sr/generator-prostih-brojeva-online/) ([Markdown](https://acrafto.com/sr/generator-prostih-brojeva-online/index.md))
- Македонски (mk): [Генератор на прости броеви](https://acrafto.com/mk/generator-na-prosti-broevi/) ([Markdown](https://acrafto.com/mk/generator-na-prosti-broevi/index.md))
- Bosanski (bs): [Generator prostih brojeva](https://acrafto.com/bs/generator-prostih-brojeva/) ([Markdown](https://acrafto.com/bs/generator-prostih-brojeva/index.md))
- Shqip (sq): [Gjenerator numrash të thjeshtë](https://acrafto.com/sq/gjenerator-numrash-te-thjeshte/) ([Markdown](https://acrafto.com/sq/gjenerator-numrash-te-thjeshte/index.md))
- Türkçe (tr): [Asal sayı bulucu](https://acrafto.com/tr/asal-sayi-olusturucu/) ([Markdown](https://acrafto.com/tr/asal-sayi-olusturucu/index.md))
- 日本語 (ja): [素数一覧・生成ツール](https://acrafto.com/ja/online-prime-number-generator/) ([Markdown](https://acrafto.com/ja/online-prime-number-generator/index.md))
- 한국어 (ko): [소수 구하기](https://acrafto.com/ko/prime-number-generator/) ([Markdown](https://acrafto.com/ko/prime-number-generator/index.md))
- العربية (ar): [مولد الأعداد الأولية](https://acrafto.com/ar/prime-number-generator/) ([Markdown](https://acrafto.com/ar/prime-number-generator/index.md))
- हिन्दी (hi): [अभाज्य संख्या जनरेटर](https://acrafto.com/hi/prime-generator/) ([Markdown](https://acrafto.com/hi/prime-generator/index.md))
- Bahasa Indonesia (id): [Generator bilangan prima](https://acrafto.com/id/generator-bilangan-prima-online/) ([Markdown](https://acrafto.com/id/generator-bilangan-prima-online/index.md))
- Tiếng Việt (vi): [Trình tạo số nguyên tố](https://acrafto.com/vi/bo-tao-so-nguyen-to-truc-tuyen/) ([Markdown](https://acrafto.com/vi/bo-tao-so-nguyen-to-truc-tuyen/index.md))
- ไทย (th): [หาจำนวนเฉพาะ](https://acrafto.com/th/prime-number-generator/) ([Markdown](https://acrafto.com/th/prime-number-generator/index.md))
- עברית (he): [מחולל מספרים ראשוניים](https://acrafto.com/he/prime-number-generator/) ([Markdown](https://acrafto.com/he/prime-number-generator/index.md))