Онлайн генератор простих чисел

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

Просте число — це натуральне число, більше за 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 – ключі генеруються з двох великих простих чисел
• Діффі-Геллман – обмін ключами за модулем простого числа
• Хеш-функції – прості числа як магічні константи (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

Часті запитання (FAQ)