Online Prímszám Generátor

Mi a prímszám?

A prímszám olyan 1-nél nagyobb természetes szám, amely csak 1-gyel és önmagával osztható. A legkisebb prímszámok: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… A 2 az egyetlen páros prímszám – az összes többi páros szám osztható kettővel.

Az olyan számok, mint a 4 (= 2 × 2), 6 (= 2 × 3) vagy 15 (= 3 × 5) nem prímszámok – ezeket összetett számoknak nevezzük.

Hogyan működik a generátor?

Az összes prímszám tartományon belüli listázásához az Eratoszthenész szitáját használjuk – az egyik legrégebbi és leghatékonyabb algoritmust, amelyet a kürenei görög matematikus, Eratoszthenész írt le Kr.e. 240 körül.

Az algoritmus szisztematikusan kihúzza az összes megtalált prímszám többszöröseit. Ami megmarad, azok a prímszámok. Az összes számítás közvetlenül a böngészőjében történik – nem küld adatokat a szerverre.

A véletlenszerű kiválasztáshoz a generátor először összeállítja a tartományban lévő összes prímszám listáját, majd abból véletlenszerűen kiválasztja a kívánt számot egy kriptográfiailag biztonságos generátor (crypto.getRandomValues()) segítségével.

A generátor funkciói

• Összes prímszám – kiírja a megadott tartományban lévő összes prímszámot (max. 10 000)
• Véletlenszerű kiválasztás – N véletlenszerű prímszámot választ ki a tartományból (nagy tartományokhoz alkalmas)
• Rendezés – az eredményeket növekvő sorrendbe rendezi
• Elválasztó – válassza ki, hogyan legyenek elválasztva a számok másoláskor
• Gyors beállítások – a leggyakoribb tartományok egy kattintással

Hol használják a prímszámokat?

Kriptográfia és biztonság

A prímszámok a modern kriptográfia alapjai. Az olyan algoritmusok, mint az RSA, azon az elven működnek, hogy két nagy prímszám szorzatát könnyű kiszámolni, de a prímtényezőkre való visszafejtés számításigényes.

• RSA titkosítás – a kulcsokat két nagy prímszámból generálják
• Diffie-Hellman – kulcscsere prímszám modulon keresztül
• Hash függvények – prímszámok mágikus konstansként (SHA, MD5)

Matematika és tudomány

• Számelmélet – az egész számok alapvető építőkövei
• Goldbach-sejtés – minden 2-nél nagyobb páros szám kifejezhető két prímszám összegeként (ez még nem bizonyított)
• Riemann-hipotézis – a Hilbert-problémák egyike, a prímszámok eloszlásával foglalkozik

Gyakorlati felhasználás

• Hash táblák – a tábla mérete prímszámként csökkenti az ütközéseket
• Pszeudovéletlen számgenerátorok – lineáris kongruencia prímszám modulussal
• Zene és ritmus – poliritmusok prímszám hosszúságú ciklusokkal

Prímszámok eloszlása

A prímszámok szabálytalanul oszlanak el a természetes számok között, de sűrűségük a tartomány növekedésével csökken. Ezt a Prímszámtétel írja le: az N-ig terjedő prímszámok száma hozzávetőlegesen N / ln(N).

Eratoszthenész szitája lépésről lépésre

Tartomány 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. Válaszd a 2-t, húzd ki a többszöröseit: 4, 6, 8, 10, 12...
2. Válaszd a 3-at, húzd ki a többszöröseit: 9, 15, 21, 27...
3. Válaszd az 5-öt, húzd ki a többszöröseit: 25...
4. √30 ≈ 5.5 → kész

Prímszámok: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Eratoszthenész szitája kódban

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

Gyakran Ismételt Kérdések (GYIK)