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

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

Простото число е естествено число, по-голямо от 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).

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

Диапазон 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

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