Онлајн генератор на прости броеви

Што е прост број?

Прост број е природен број поголем од 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

Често поставувани прашања (ЧПП)