# Генератор на прости числа

> Изведете всички прости числа в диапазон или изберете N произволни. Ситото на Ератостен смята незабавно направо в браузъра – без сървър.

URL: https://acrafto.com/bg/generator-na-prosti-chisla-onlajn/

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.

## Какво е просто число?

**Простото число** е естествено число, по-голямо от 1, което се дели само на 1 и на себе си. Най-малките прости числа са 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… Числото 2 е единственото четно просто число – всички останали четни числа се делят на две.

Числа като 4 (= 2 × 2), 6 (= 2 × 3) или 15 (= 3 × 5) **не са** прости числа – наричаме ги съставни числа.

## Как работи генераторът?

За извеждане на всички прости числа в даден диапазон използваме **ситото на Ератостен** – един от най-старите и ефективни алгоритми, описан от гръцкия математик Ератостен от Кирена около 240 г. пр. н. е.

Алгоритъмът постепенно изключва кратните на всяко намерено просто число. Това, което остава, са простите числа. Цялото изчисление се извършва **директно във вашия браузър** – никакви данни не се изпращат до сървъра.

За произволен избор генераторът първо изгражда списък на всички прости числа в диапазона и след това произволно избира необходимия брой от тях, използвайки криптографски сигурен генератор (`crypto.getRandomValues()`).

## Функции на генератора

- **Всички прости числа** – извежда всяко просто число в дадения диапазон (макс. 10 000)
- **Произволен избор** – избира N произволни прости числа от диапазона (подходящо за големи диапазони)
- **Сортиране** – сортирайте резултатите във възходящ ред
- **Разделител** – изберете как ще бъдат разделени числата при копиране
- **Бързи предварителни настройки** – най-често използваните диапазони с едно кликване

## Къде се използват простите числа?

### Криптография и сигурност

Простите числа са в основата на съвременната криптография. Алгоритми като **RSA** работят на принципа, че произведението на две големи прости числа е лесно за изчисляване, но обратното разлагане на прости множители е изчислително много трудно.

- **RSA криптиране** – ключовете се генерират от две големи прости числа
- **Diffie-Hellman** – обмен на ключове по прост модул
- **Хеш функции** – прости числа като магически константи (SHA, MD5)

### Математика и наука

- **Теория на числата** – основни градивни елементи на целите числа
- **Хипотеза на Голдбах** – всяко четно число > 2 може да бъде изразено като сума от две прости числа (все още недоказана)
- **Хипотеза на Риман** – един от проблемите на Хилберт, отнасящ се до разпределението на простите числа

### Практическо приложение

- **Хеш таблици** – размерът на таблицата като просто число намалява колизиите
- **Генератори на псевдослучайни числа** – линейна конгруенция с прост модул
- **Музика и ритъм** – полиритми с прости дължини на цикъла

## Разпределение на простите числа

Простите числа са разпределени неравномерно сред естествените числа, но тяхната плътност намалява с увеличаването на диапазона. Това се описва от **Теоремата за разпределението на простите числа**: броят на простите числа до N е приблизително N / ln(N).

| Диапазон | Брой прости числа |
| --- | --- |
| 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 |

## Ситото на Ератостен стъпка по стъпка

```
Диапазон 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. Изберете 2, зачеркнете кратните: 4, 6, 8, 10, 12...
2. Изберете 3, зачеркнете кратните: 9, 15, 21, 27...
3. Изберете 5, зачеркнете кратните: 25...
4. √30 ≈ 5.5 → готово

Прости числа: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
```

## Ситото на Ератостен в код

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

## Често задавани въпроси (ЧЗВ)

### Единицата просто число ли е?

Не. Числото 1 традиционно не се счита за просто число. Причината е математическа – ако считахме 1 за просто число, теоремата за еднозначното разлагане на прости множители би загубила своята валидност.

### Двойката просто число ли е?

Да. Числото 2 е най-малкото и същевременно единственото четно просто число. Всички останали четни числа се делят на две, т.е. са съставни.

### Колко прости числа съществуват?

Безкрайно много. Евклид е доказал това около 300 г. пр. н. е. с елегантно доказателство чрез противоречие: да предположим, че съществуват краен брой прости числа. Тогава тяхното произведение + 1 не може да се дели на нито едно от тях – следователно това е ново просто число, противоречие.

### Какво представляват простите числа близнаци?

Простите числа близнаци са двойки прости числа, които се различават с 2, например (3, 5), (11, 13), (17, 19), (41, 43). Дали съществуват безкрайно много такива, е все още нерешен въпрос в математиката (Хипотеза за простите числа близнаци).

### Колко бързо работи алгоритъмът?

Ситото на Ератостен има времева сложност O(n log log n). За диапазон до 10 милиона изчислението в браузъра обикновено отнема под 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))
- 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))
- Lietuvių (lt): [Pirminių skaičių generatorius](https://acrafto.com/lt/pirminiu-skaiciu-generatorius/) ([Markdown](https://acrafto.com/lt/pirminiu-skaiciu-generatorius/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))