Prímszám-ellenőrző
Ellenőrizze, hogy egy szám prímszám-e, és találja meg a tényezőit. Ingyenes prímszám-ellenőrző, amely azonnal teszteli bármelyik számot. Regisztráció nélkül.
Mi az a prímszám?
Egy prímszám természetes szám, amely nagyobb 1-nél, és pontosan két különböző osztója van: 1 és maga. Az első prímszámok: 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...
A prímszámok fontos tényei:
- 2 az egyetlen páros prímszám. Minden más páros szám osztója van, tehát több, mint két osztója van.
- 1 nem prímszám a modern konvenció szerint. Az 1 kihagyása megőrzi a prímszámok osztályozásának egyediségét (Alapvető Összefüggés).
- A prímszámok végtelenek. Euclid bizonyította ezt kb. 300 évvel ezelőtt: feltételezzük, hogy van egy véges lista a prímszámokból p₁, p₂, ..., pₙ. Akkor a szám (p₁ × p₂ × ... × pₙ) + 1 prímszám vagy prímszámfaktor nélküli - ellentmondás. Ezért a lista végtelen.
- Az osztályozás növekedésével a prímszámok ritkábbak lesznek - de soha nem állnak meg. 25 prímszám van 100 alatt, 168 1000 alatt, és 78 498 1 000 000 alatt.
Egy közepes szám bármely pozitív egész szám, amely nagyobb 1-nél, és nem prímszám - legalább egy olyan osztója van, amely nem 1 és maga. A szám 12 közepes, mert 12 = 2 × 6 = 3 × 4 = 2 × 2 × 3. Minden közepes számnak egyedi prímszám-felbontása van (Alapvető Összefüggés).
Hogyan ellenőrizhetjük, hogy egy szám prímszám-e?
Számos módszer létezik a prímszám-tesztelésre, a egyszerű próbálkozásos eljárástól a kriptográfiai alkalmazásokig:
Próbálkozásos eljárás (alapvető módszer): Próbáljuk meg, hogy bármely egész számot 2-től √n-ig osztja-e n. Ha nem, akkor n prímszám. Csak a √n-ig kell ellenőrizni, mert ha n = a × b azzal, hogy a ≤ b, akkor a ≤ √n. Ha n-nél nincs osztó √n-ig, akkor n-nél sincs.
Optimált próbálkozásos eljárás: A 2 után ellenőrizni kell az páratlan számokat. Továbbá: ellenőrizni kell a 2-t, a 3-at, majd csak a 6k ± 1 formájú számokat (mivel minden prímszám > 3 ebből a formából van). Ez a módszer a naiv próbálkozásos eljárásnál mintegy 66%-kal csökkenti a tesztek számát.
| Szám | √n (megközelítés) | Próbálkozásos eljárásig | Prímszám? |
|---|---|---|---|
| 97 | 9,85 | 2, 3, 5, 7 | Igen (nincs osztó) |
| 91 | 9,54 | 2, 3, 5, 7 | Nem (7 × 13 = 91) |
| 1 009 | 31,76 | 31-ig | Igen (prímszám) |
| 1 001 | 31,64 | 31-ig | Nem (7 × 11 × 13 = 1 001) |
| 7 919 | 88,99 | 89-ig | Igen (a 1000. prímszám) |
A nagy számok (százak számjegyei) számára a próbálkozásos eljárás számítási szempontból nem hajtható végre. A Miller-Rabin prímszám-teszt (valószínűségi, kriptográfiai alkalmazás) és a AKS prímszám-teszt (determinisztikus polinomiális idő, 2002) használata helyettesíti.
Prímösztékelés
Minden összetett szám egyedi prímszorzatú alakban írható fel — prímösztékelésével. Ez garantálódik az Arisztotelész általános alaptételének. A prímösztékelés meghatározásához ismételten osztani kell a legkisebb prímfaktorral:
| Szám | Prímösztékelés | Faktorfa bontás |
|---|---|---|
| 12 | 2² × 3 | 12 → 4×3 → 2×2×3 |
| 60 | 2² × 3 × 5 | 60 → 4×15 → 2²×3×5 |
| 100 | 2² × 5² | 100 → 4×25 → 2²×5² |
| 360 | 2³ × 3² × 5 | 360 → 8×45 → 2³×3²×5 |
| 1024 | 2¹⁰ | Összes prímfaktor 2 |
| 2310 | 2 × 3 × 5 × 7 × 11 | Terméke a 5 első prímeknek |
A prímösztékelés használható a legnagyobb közös osztó (GCD) és a legkisebb közös többszörös (LCM) meghatározására. GCD(12, 18) = 2² × 3? Nem — vegye a megosztott prímszámok minimális hatalmát: GCD = 2¹ × 3¹ = 6. A LCM a maximális hatalmat veszi: LCM(12, 18) = 2² × 3² = 36.
Miért fontosak a prímek: a matematika és a technológia alkalmazásai
A prímek az aritmetika "atomjai" — az Arisztotelész általános alaptétel kimondja, hogy minden pozitív egész szám, amely nagyobb 1-nél, vagy prím, vagy egyedi prímszorzatú alakban kifejezhető. Ez a egyediség teszi a prímet az összes szám építőkövévé.
A modern internetbiztonság a prímszámokon múlik. Az RSA-védelem (használják HTTPS, e-mail- és digitális aláírások védelmére) két nagy prímet, p-t és q-t használ a nyilvános kulcs létrehozásához, ahol n = p × q. A titkosítás és a dekódolás kulcsai a moduláris aritmetikával számítódnak ki n-nel. A biztonság a teljes számok faktorizálásának függvényében áll: adott n (2048 bites szám, ~617 decimális jeggyel), a p és q meghatározása számítógéppel nem hajtható végre.
A Diffie-Hellman kulcsátvétel nagy prímet használ modulusként a biztonságos kulcsmegállapodáshoz. Amikor HTTPS-n keresztül csatlakozik egy webhelyhez, a prímszámok titokban védik adatait valós időben.
A hash táblák prímszámú tömböket használnak a keresési kísérletek minimalizálásához. Amikor egy hash függvény a kulcsokat tároló indexekre mapolja, a prímszámú tömbök használata jobb elosztást eredményez, mert a prímszámoknak nincsenek olyan tényezői, amelyek rendszeres keresési mintákat okoznának.
A pseudorandom számgenerátorok (PRNG) prímszámokat használnak a lineáris kongruenciális generátorokban és más algoritmusokban. A periódus (ismétlés előtt) ilyen generátorok gyakran egyenlő a prímszám modulussal egyenlő 1-gyel.
Speciális prímtípusok
A végtelen prímszámok halmazában bizonyos alkatrészek különleges tulajdonságokkal rendelkeznek vagy jelentőséggel bírnak:
| Típus | Definíció | Példák |
|---|---|---|
| Twin prímszámok | 2-vel különböző prímek | (3,5), (11,13), (17,19), (41,43) |
| Mersenne prímszámok | 2ⁿ - 1 alakú prímek | 3, 7, 31, 127, 8191 |
| Fermat prímszámok | 2^(2ⁿ) + 1 alakú prímek | 3, 5, 17, 257, 65537 |
| Sophie Germain prímszámok | p és 2p+1 prímek | 2, 3, 5, 11, 23, 29 |
| Palindrom prímszámok | Prímek, amelyek előre-hátra olvasva ugyanazok | 11, 101, 131, 151, 181 |
| Safe prímszámok | (p-1)/2 prím | 5, 7, 11, 23, 47, 59 |
A Mersenne prímszámok (2ⁿ - 1) különösen fontosak, mert prímszámosságukat a hatékony Lucas-Lehmer teszttel lehet ellenőrizni. A GIMPS (Great Internet Mersenne Prime Search) projekt a világszerte elosztott számítógépek segítségével új Mersenne prímszámokat keres. 2024-ig a legnagyobb ismert Mersenne prímszám a 2^136,279,841 - 1, amelynek több mint 41 millió decimális jegye van.
A twin prímszámok (párok, amelyek 2-vel különböznek) végtelennek vannak (twin prímszámok végtelen konjectúrája), de ez a probléma még nem bizonyított — egyik legismertebb nyitott probléma a matematikában. 2013-ban Yitang Zhang bizonyította a gyengébb eredményt, hogy végtelen számú prímpárok vannak, amelyek legfeljebb 70 millióval különböznek egymástól, amelyet később 246-ra javítottak.
A prímszámok eloszlása
A prímszámok ritkábban fordulnak elő, ahogy a számok nagyobbak lesznek, de eloszlásuk statisztikai mintákat követ, amelyeket a prímszám-tétel ír le:
A prímszám-tétel (Hadamard és de la Vallée-Poussin 1896-ban függetlenül bebizonyította) kimondja, hogy a N-ig lévő prímszámok száma, amelyet π(N)-nek nevezünk, nagy N-re közelítőleg N / ln(N) a következő:
| N | Valós π(N) | N/ln(N) közelítése | Sűrűség |
|---|---|---|---|
| 100 | 25 | 21,7 | 1:4 |
| 1,000 | 168 | 144,8 | 1:6 |
| 10,000 | 1,229 | 1,085,7 | 1:8 |
| 100,000 | 9,592 | 8,685,9 | 1:10 |
| 1,000,000 | 78,498 | 72,382,4 | 1:13 |
| 1,000,000,000 | 50,847,534 | 48,254,942 | 1:20 |
A Riemann-hipotézis — egy millió dolláros díjat kínáló egyik Millennium-díjas probléma — a prímszámok pontos eloszlásáról szól. A hipotézis azt feltételezi, hogy a Riemann zéta-függvény nem-triviális zérusai valós része 1/2. Ez kapcsolódik ahhoz, hogy "véletlenszerű" a prímszámok eloszlása — a hipotézis előre jelezte a prímszámok közötti optimális rendet.
Foglalkozó kérdések
Van-e 1 prímszám?
Nem. A modern matematikai konvenció szerint a 1 nem prímszám, nem pedig kombinált szám. A prímszámok egyediségét megőrizve kizárjuk a 1-et a prímszámok közül (a számelmélet alapfogalmai) — ha a 1 prímszám lenne, minden szám végtelen sok faktorizálásra lenne képes (pl. 6 = 2×3 = 1×2×3 = 1×1×2×3 = ...). Történetileg néhány matematikus a 1-et is prímnak tekintette, de a modern definíció kizárja.
Milyen a legnagyobb ismert prímszám?
2024-ig a legnagyobb ismert prímszám a 2^136,279,841 − 1 (Mersenne-prím), amelyet októberben fedeztek fel. Több mint 41 millió számjegyet tartalmaz. A Nagy Internetes Mersenne-prím-kutatási projekt (GIMPS) a legtöbb rekordprímet a világon elosztott számítással találja meg. Ezek a hatalmas prímszámok nincsenek gyakorlati alkalmazásban — kizárólag matematikai felfedezés céljából kutatják őket.
Vannak-e minták a prímszámokban?
A prímszámok tűnik, hogy nem rendelkeznek mintákkal, de léteznek. Minden prímszám > 5 vége 1, 3, 7 vagy 9 (soha nem 0, 2, 4, 5, 6 vagy 8). Minden prímszám > 3 a 6k±1 formátumú. A kettős prímszámok (2-vel különbözőek, például 11 és 13) úgy tűnik, hogy végtelenül folytatódnak (twin prímszám-hipotézis). A prímszámok számelméleti sűrűségét a prímszámok közelében a Prímszámok számelméleti tétel leírja, mint körülbelül 1/ln(N).
2 prímszám-e?
Igen, a 2 prímszám — és az egyetlen páros prímszám. A 2 pontosan két faktora van (1 és 2), amely megfelel a definíciónak. Minden más páros szám osztható a 2-vel, tehát kombinált szám. A 2 prímságának különleges esete gyakran szükséges külön kezelni algoritmusokban és bizonyításokban.
Hogyan használják a prímszámokat a titkosításban?
A RSA titkosítás generál egy kulcs-párt: (1) két nagy prímet választanak p és q (minden 1024+ bit), (2) számolják ki n = p×q-t, (3) deriválják a titkosítási kulcsot e és a visszafejtési kulcsot d a moduláris aritmetikával. Bárki titkosíthat n és e segítségével (nyilvános kulcs), csak a p és q (vagy d) birtokosának van lehetősége visszafejteni. A biztonság a n faktorizálásának számítási nehézségében rejlik.
Milyen a leggyorsabb módja annak, hogy ellenőrizze, hogy egy szám prímszám-e?
Kis számok esetén (10^12-ig): optimalizált próbálkozásos ellenőrzés a √n-ig, a 6k±1 minta használatával. Közepes számok esetén: Miller-Rabin prímszám-ellenőrzés néhány tanúval valószínűségi, de rendkívül gyors. Nagy számok esetén (kriptográfiai méret, 1000+ számjegy): valószínűségi tesztek, például a Miller-Rabin több random tanúval, vagy az AKS teszt a determinisztikus bizonyításra.
Mi a prímszám-arány?
A prímszám-arány a két egymást követő prímszám közötti különbség. A legkisebb prímszám-arány 1 (a 2 és a 3 között), és a többi egymást követő prímszám-arány legalább 2 (mivel az egyiknek párosnak kell lennie). Az árnyak lassan növekednek átlagosan: a közelében N, a prímszámok átlagos árnya körülbelül ln(N). Kivételesen nagy prímszám-arányok léteznek — léteznek végtelen hosszú sorok egymást követő kombinált számok (n!+2, n!+3, ..., n!+n összes kombinált szám bármely n esetén).
A 100 prímszámjainak tényezői?
100 = 2 × 50 = 2 × 2 × 25 = 2 × 2 × 5 × 5 = 2² × 5². A 100 prímtényezői a 2 és a 5. A tényezőzés magyarázza, hogy a 100 osztja megfelelően a 1, 2, 4, 5, 10, 20, 25, 50 és 100-ot — mindegyik osztó egy kombinációja a 2⁰˒¹˒² és a 5⁰˒¹˒².
Mi a Goldbach-sejtés?
Goldbach-sejtés (1742): minden páros szám > 2 kifejezhető két prímszám összegének. Példa: 4=2+2, 6=3+3, 8=3+5, 10=3+7, 100=3+97=11+89=17+83. Számításilag ellenőrizték 4×10^18-ig, de meg nem bizonyított. Az egyik legrégebbi és legismertebb megoldatlan probléma a számelméletben.
Hány prímszám létezik?
Van végtelen sok prímszám — Eukleidész bizonyította ezt kb. 300 BC-ben. A bizonyítás ellentmondás: ha a prímszámok végesek lennének, akkor a természetes számok összege plusz 1 prímszám lenne vagy prímtényezőkkel rendelkező szám lenne, amely nem szerepel a feltételezett teljes listában, ellentmondás. Bár a prímszámok ritkábban fordulnak elő nagyobb számoknál, soha nem állnak meg. 1 millió alatt 78 498 prímszám és 100 millió alatt 5 761 455 prímszám van.
Prímszámok a számelméletben és megoldatlan problémák
Prímszámok a számelmélet legszebb és legkeményebben megoldatlan problémáinak közepén állnak. Ezeket az nyitott kérdéseket megértve világosabbá válik, hogy mennyit tudunk a prímszámokról – és hogy mennyi maradt még rejtett a századok óta tartó erőfeszítések ellenére.
Riemann-hipotézis (1859): A Riemann-zéta-függvény ζ(s) = Σ(1/nˢ) kapcsolatban áll a prímszámok eloszlásával a nullpontjainak elhelyezkedésével. A hipotézis állítása szerint a nem-triviális nullpontok a kritikus vonalon, Re(s) = 1/2 helyezkednek el. Ha igaz, akkor a legpontosabb leírás lenne a prímszámok eloszlásáról. Több mint 10 trillió nullpontot számoltak ki, és mindegyik a kritikus vonalon helyezkedik el – de nincs bizonyítás. A Clay Mathematics Institute-től 1 millió dolláros díjat kínál a megoldásáért.
Twin Prime Konjectúra: Vannak-e végtelen sok páros prímpárra (p, p+2) – mint (11,13), (17,19), (41,43), (101,103)? A konjectúra azt állítja, hogy igen, de nem bizonyították. 2013-ban Yitang Zhang megtalálta a prímpárok végtelen sokiságát bizonyító általánosítást, amely szerint a párok közötti különbség legfeljebb 70 millió. A Polymath Projekt később ezt a határt 246-ra csökkentette, ami azt jelenti, hogy tudjuk, hogy végtelen sok olyan prímpár van, amelynek a különbsége ≤ 246. A 2-es különbség még nem bizonyított.
Goldbach-sejtés (1742): Minden páros szám, amely nagyobb, mint 2, két prímszám összege. Számításokkal ellenőrizték 4 × 10^18-ig. Minden páros szám, amelyet eddig kipróbáltak, kielégíti a sejtést – gyakran sokféleképpen (100 = 3+97 = 11+89 = 17+83 = 29+71 = 41+59 = 47+53). De nincs bizonyítás, amely fedezné az összes páros számot. A "gyenge Goldbach-sejtés" (minden páratlan szám ≥ 7 két prímszám összege) 2013-ban bizonyították Harald Helfgotttal.
Mersenne-prímek és tökéletes számok: A Mersenne-prím egy olyan prímszám, amelynek a formája 2ⁿ − 1 (ahol n maga is prímszám kell, hogy legyen). Az első néhány példa: 3, 7, 31, 127, 8191. 2024-ig 52 ilyen ismert. A Mersenne-prímek kapcsolatban állnak a tökéletes számokkal: minden Mersenne-prím generál egy páros tökéletes számot a 2^(p−1) × (2^p − 1) formulával. A 28 = 4 × 7 (a Mersenne-prím 7 használatával) és a 496 = 16 × 31 (a Mersenne-prím 31 használatával) tökéletes számok. Vannak-e végtelen sok Mersenne-prím? Ismeretlen.
ABC-sejtés és annak következményei: Az ABC-sejtés (1985-ben megfogalmazva) egy mély kapcsolatot ír le a három szám faktorizációjáról a = b + c. Ha igazolják, akkor Fermat utolsó tételét és sok más eredményt könnyen következtetni lehet belőle. 2012-ben Shinichi Mochizuki publikálta a bizonyítását, amely az Inter-universal Teichmüller elméletet használja – de a bizonyítás olyan új és összetett, hogy a matematikai közösség több mint egy évtizede vitatja annak érvényességét, néhány matematikus elfogadja, mások pedig hiányt találnak.
Prímszámok a matematika legnagyobb rejtélyei: egyszerűen definiálhatók (pontosan két faktoruk van), de eloszlásuk olyan összetett, hogy megoldatlan problémákat rejtenek magukban, amelyekkel a legnagyobb matematikusok is küzdöttek századok óta. Minden újabb prímszám, amelyet felfedeznek, minden újabb számítási ellenőrzés, amelyet egy sejtés határáig elvégeznek, és minden részleges bizonyítás, amelyet megtalálnak, előrébb viszi a megértést – miközben emlékeztet arra, hogy mennyi még megoldatlan maradt.