Prímszám kalkulátor

Prímszám kalkulátor - Összeg, darabszám és prímszám-keresés

🔢 Számítsd ki a prímszámok összegét, keress prímeket egy tartományban, ellenőrizd, hogy egy szám prímszám-e, és találd meg az n-edik prímszámot. Gyors Eratoszthenész-szita algoritmus vizualizációval.

Mik azok a prímszámok?

A prímszám 1-nél nagyobb természetes szám, amely nem állítható elő két kisebb természetes szám szorzataként. Másképp: pontosan két osztója van: 1 és önmaga.

Az első 25 prímszám

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Hogyan ellenőrizhető, hogy egy szám prímszám-e?

1. módszer – Próbaosztás:

• Ellenőrizd, hogy n osztható-e bármely számmal 2-től √n-ig
• Ha igen, összetett (nem prím)
• Ha nem, prím

Példa: 17 prím?

• √17 ≈ 4.12, ezért 2-vel, 3-mal és 4-gyel vizsgáljuk az oszthatóságot
• 17 ÷ 2 = 8.5 (nem osztható)
• 17 ÷ 3 = 5.67 (nem osztható)
• 17 ÷ 4 = 4.25 (nem osztható)
• Eredmény: 17 prím!

Eratoszthenész szitája

Ősi algoritmus az összes prímszám megtalálására n-ig:

• 1. lépés: Írd fel a 2-től n-ig terjedő számokat
• 2. lépés: Jelöld a 2-t prímszámként, és húzd ki a 2 többszöröseit
• 3. lépés: Keresd meg a következő kihúzatlan számot (3), és jelöld prímszámnak
• 4. lépés: Húzd ki az adott prímszám többszöröseit
• 5. lépés: Ismételd √n-ig
• Eredmény: A kihúzatlan számok prímek

Prímszámok összege

Az első n prím összege:

• Első 10 prím: 2+3+5+7+11+13+17+19+23+29 = 129
• Első 100 prím: összeg = 24 133
• Első 1000 prím: összeg = 3 682 913

Prímek összege n-ig:

• 10-ig: 2+3+5+7 = 17
• 100-ig: összeg = 1 060
• 1000-ig: összeg = 76 127

Prímszám-tétel

Az n-nél kisebb prímek száma megközelítőleg n/ln(n):

• 100-ig: ~25 prím (valós: 25)
• 1 000-ig: ~145 prím (valós: 168)
• 10 000-ig: ~1 086 prím (valós: 1 229)
• 100 000-ig: ~8 686 prím (valós: 9 592)

Prímszámok típusai

Prím ikrek: Olyan prímek, amelyek különbsége 2

• (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)...

Mersenne-prímek: 2ᵖ - 1 alakú számok, ahol p prím

• 2² - 1 = 3
• 2³ - 1 = 7
• 2⁵ - 1 = 31
• 2⁷ - 1 = 127
• A legnagyobb ismert prímszám Mersenne-prím (24,8 millió számjegy!)

Sophie Germain-prímek: Olyan prím p, amelyre 2p+1 szintén prím

• 2 (2×2+1 = 5), 3 (2×3+1 = 7), 5 (2×5+1 = 11), 11, 23, 29...

Fermat-prímek: 2^(2ⁿ) + 1 alakú számok

• F₀ = 3, F₁ = 5, F₂ = 17, F₃ = 257, F₄ = 65,537
• Csak 5 ismert Fermat-prím létezik

Prímszámok alkalmazásai

Kriptográfia (RSA):

• A nagy számok faktorizálásának nehézségén alapul
• Két nagy prímszámot használ (százas nagyságrendű számjegyek)
• Védi az online bankolást, e-maileket és weboldalakat

Hash táblák:

• Prím méretű hash táblák csökkentik az ütközéseket
• Adatbázisokban és cache-elésben használatos

Véletlenszám-generálás:

• A prímek jobb pszeudo-véletlen sorozatokat adhatnak
• Szimulációkban és játékokban használatos

Érdekességek a prímszámokról

• Végtelenség: Eukleidész ~Kr. e. 300 – a prímek sosem fogynak el
• Hézagok: tetszőlegesen nagyok lehetnek
• Goldbach-sejtés: minden páros szám > 2 két prím összege (nem bizonyított!)
• Riemann-sejtés: „millió dolláros” probléma a prímek eloszlásáról
• Prímhézagok: a szomszédos prímek különbsége általában nő
• Valószínűség: egy véletlen n szám kb. 1/ln(n) eséllyel prím

Rekordok

• Legnagyobb ismert prímszám: 2^82,589,933 - 1 (2018, 24,862,048 számjegy)
• Legnagyobb prím ikrek: 2,996,863,034,895 × 2^1,290,000 ± 1
• Számítás: GIMPS (Great Internet Mersenne Prime Search) elosztott projekt

Gyakori tévhitek

• Az 1 NEM prím: modern definíció szerint (pontosan 2 osztó kell)
• Nem minden páratlan prím: 9, 15, 21, 25... összetett
• „Minden prímet adó képlet”: nincs egyszerű képlet, ami az összes prímet adja
• Minta a prímekben: nincs előre jelezhető minta (látszólag véletlenszerűek)

💡 Pro tipp: Nagy szám primalitásának vizsgálatánál elég a négyzetgyökéig tesztelni az oszthatóságot! Például 997 esetén √997 ≈ 31,6, így elég 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 osztókat próbálni. Ha egyik sem osztja maradék nélkül, akkor prím. Ráadásul (2 és 3 kivételével) minden prím a 6k±1 alakú, ami tovább gyorsíthat.