Ett primtal är ett heltal större än 1 som har exakt två faktorer: 1 och sig själv. Primtal är byggstenarna i alla heltal - varje heltal kan uttryckas som en produkt av primtal.
De första 25 primtalen
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
Observera att 2 är det enda jämna primtalet. Alla andra jämna tal är delbara med 2.
Metod 1: Trial Division
Det enklaste sättet att testa om ett tal är primtal — kontrollera om något tal upp till kvadratroten delar det jämnt.
Nyckelinsikt: Om n har en faktor som är större än √n, har den också en motsvarande faktor som är mindre än √n. Så du behöver bara kontrollera upp till √n.
Algoritm:
- Om n < 2, inte primtal
- Om n = 2, prim
- Om n är jämnt (förutom 2), inte primtal
- Kontrollera alla udda tal från 3 till √n
- Om någon dela n jämnt, inte grunda
- Fyll annars
Exempel: Är 97 prime?
√97 ≈ 9,85, så kontrollera primtal upp till 9: 2, 3, 5, 7
- 97 ÷ 2 = 48,5 (inte hela)
- 97 ÷ 3 = 32,33... (inte hel)
- 97 ÷ 5 = 19,4 (inte hela)
- 97 ÷ 7 = 13,86 (inte hela)
Inga delare hittades — 97 är primtal.
Exempel: Är 91 prime?
√91 ≈ 9,54, kontrollera upp till 9: 2, 3, 5, 7
- 91 ÷ 7 = 13 (hela tal!)
91 är inte primtal — 91 = 7 × 13.
Metod 2: Sil av Eratosthenes
Eratosthenessikten hittar alla primtal upp till en given gräns. Den är snabb och elegant, uppfunnen av den grekiske matematikern Eratosthenes runt 240 f.Kr.
För att hitta alla primtal upp till 50:
- Skriv ut siffrorna 2 till 50
- Börja med 2 (första primtal). Stryk ut alla multiplar av 2 (4, 6, 8...)
- Flytta till nästa icke-kryssade tal: 3. Stryk ut multiplar av 3 (9, 15, 21...)
- Nästa okryssade: 5. Stryk ut multiplar av 5 (25, 35...)
- Nästa okryssade: 7. Stryk ut multiplar av 7 (49...)
- Stanna när du når √50 ≈ 7.07
- Alla återstående okorsade tal är primtal
Primmar upp till 50: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
Primes upp till 100: Komplett lista
| Räckvidd | 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 |
Det finns 25 primtal under 100.
Snabba delbarhetstester
Innan du gör full division, kontrollera dessa regler:
| Delbart med | Om... |
|---|---|
| 2 | Sista siffran är jämn (0,2,4,6,8) |
| 3 | Summan av siffror delbar med 3 |
| 5 | Sista siffran är 0 eller 5 |
| 7 | Ingen enkel regel - bara dela |
| 11 | Växelvis siffror delbar med 11 |
Exempel: Är 143 primtal? – Inte ens ✓
- 1+4+3 = 8, ej delbart med 3 ✓
- Slutar inte på 0 eller 5 ✓
- √143 ≈ 11,96, kolla upp till 11
- 143 ÷ 7 = 20,43 ✓
- 143 ÷ 11 = 13 — delbart!
143 = 11 × 13. Inte primtal.
Varför Primes är viktiga
Kryptografi: RSA-kryptering – som används för att säkra internetbanker, HTTPS och e-post – bygger på det faktum att det är enkelt att multiplicera två stora primtal, men att faktorisera resultatet tillbaka till primtal är extremt svårt.
Datavetenskap: Hash-tabeller, slumptalsgeneratorer och kontrollsummor använder egenskaperna för primtal.
Ren matematik: Fördelningen av primtal är fortfarande ett av de djupaste olösta problemen i matematik - Riemannhypotesen.
Intressanta främsta fakta
- Det största kända primtal (från och med 2024) har över 41 miljoner siffror
- Tvillingprimtal är primtal som skiljer sig med 2 (11 och 13, 17 och 19, 41 och 43)
- Det finns oändligt många primtal — bevisade av Euklid omkring 300 f.Kr
- Goldbachs gissning (obevisad sedan 1742): varje jämnt tal > 2 är summan av två primtal