A prímszám egy 1-nél nagyobb egész szám, amelynek pontosan két tényezője van: 1 és önmaga. A prímszámok minden egész szám építőkövei – minden egész szám kifejezhető prímszámok szorzataként.
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
Figyeljük meg, hogy a 2 az egyetlen páros prímszám. Az összes többi páros szám osztható 2-vel.
1. módszer: Próbafelosztás
A legegyszerűbb módszer annak tesztelésére, hogy egy szám prím-e – ellenőrizze, hogy a négyzetgyökig terjedő szám egyenlően osztja-e.
Kulcsbetekintés: Ha n tényezője nagyobb, mint √n, akkor a megfelelő tényezője is kisebb, mint √n. Tehát csak √n-ig kell ellenőriznie.
Algoritmus:
- Ha n < 2, nem prím
- Ha n = 2, prím
- Ha n páros (kivéve 2), nem prím
- Ellenőrizze az összes páratlan számot 3-tól √n-ig
- Ha van, n egyenlően osztja, nem prím
- Ellenkező esetben alapozó
Példa: 97 prím?
√97 ≈ 9,85, ezért ellenőrizze a prímeket 9-ig: 2, 3, 5, 7
- 97 ÷ 2 = 48,5 (nem egész)
- 97 ÷ 3 = 32,33... (nem egész)
- 97 ÷ 5 = 19,4 (nem egész)
- 97 ÷ 7 = 13,86 (nem egész)
Nem található osztó — 97 prím.
Példa: 91 prím?
√91 ≈ 9,54, ellenőrzés 9-ig: 2, 3, 5, 7
- 91 ÷ 7 = 13 (egész szám!)
91 nem prím — 91 = 7 × 13.
2. módszer: Eratoszthenész szitája
Eratoszthenész szitája minden prímet megtalál egy adott határig. Gyors és elegáns, Eratoszthenész görög matematikus találta fel ie 240 körül.
Az összes prímszám megtalálása 50-ig:
- Írja ki a számokat 2-től 50-ig
- Kezdje 2-vel (első prím). Húzd át a 2 többszörösét (4, 6, 8...)
- Lépjen a következő át nem keresztezett számra: 3. Húzza ki a 3 többszöröseit (9, 15, 21...)
- Következő át nem húzva: 5. Húzd át az 5 többszörösét (25, 35...)
- Következő áthúzatlan: 7. Húzza át a 7 többszörösét (49...)
- Álljon meg, ha eléri a √50 ≈ 7.07-et
- Az összes fennmaradó keresztezetlen szám prímszám
Akár 50-es alapozás: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
Feltöltés 100-ig: Teljes lista
| Hatótávolság | Primes |
|---|---|
| 1–10 | 2, 3, 5, 7 |
| 11–20 | 11, 13, 17, 19 |
| 21–30 | 23, 29 |
| 31–40 | 31, 37 |
| 41–50 | 41, 43, 47 |
| 51–60 | 53, 59 |
| 61–70 | 61, 67 |
| 71–80 | 71, 73, 79 |
| 81–90 | 83, 89 |
| 91–100 | 97 |
100 alatt 25 prím van.
Gyors oszthatósági tesztek
A teljes felosztás előtt ellenőrizze az alábbi szabályokat:
| Ezzel osztható | Ha... |
|---|---|
| 2 | Az utolsó számjegy páros (0,2,4,6,8) |
| 3 | 3-mal osztható számjegyek összege |
| 5 | Az utolsó számjegy 0 vagy 5 |
| 7 | Nincs egyszerű szabály – csak oszd meg |
| 11 | Váltakozó számjegyek összege osztható 11-gyel |
Példa: 143 prím?
- Még csak nem is ✓
- 1+4+3 = 8, nem osztható 3-mal ✓
- Nem 0-ra vagy 5-re végződik ✓
- √143 ≈ 11,96, ellenőrizze 11-ig
- 143 ÷ 7 = 20,43 ✓
- 143 ÷ 11 = 13 — osztható!
143 = 11 × 13. Nem prím.
Miért számítanak a primerek?
Rejtjelezés: Az RSA-titkosítás – amelyet az internetes banki szolgáltatások, a HTTPS és az e-mailek védelmére használnak – azon a tényen alapul, hogy két nagy prímszám szorzata egyszerű, de az eredményt nagyon nehéz prímszámokká számolni.
Számítástechnika: A hash-táblák, a véletlenszám-generátorok és az ellenőrző összegek prímszámok tulajdonságait használják.
Tiszta matematika: A prímszámok eloszlása továbbra is az egyik legmélyebb megoldatlan probléma a matematikában – a Riemann-hipotézis.
Érdekes legfontosabb tények
- A legnagyobb ismert prímszám (2024-ben) több mint 41 millió számjegyből áll
- Az ikerprímek olyan prímek, amelyek 2-vel különböznek (11 és 13, 17 és 19, 41 és 43)
- Végtelenül sok prímszám van – ezt Eukleidész bizonyította Kr.e. 300 körül
- Goldbach-sejtés (1742 óta nem bizonyított): minden 2-nél nagyobb páros szám két prímszám összege