Un număr prim este un număr întreg mai mare decât 1 care are exact doi factori: 1 și el însuși. Numerele prime sunt blocurile de bază ale tuturor numerelor întregi - fiecare număr întreg poate fi exprimat ca produs de numere prime.
Primele 25 de numere prime
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
Rețineți că 2 este singurul număr prim par. Toate celelalte numere pare sunt divizibile cu 2.
Metoda 1: Divizia de judecată
Cel mai simplu mod de a testa dacă un număr este prim - verificați dacă orice număr până la rădăcina pătrată îl împarte egal.
Perspectivă cheie: Dacă n are un factor mai mare decât √n, are și un factor corespunzător mai mic decât √n. Deci, trebuie să verificați doar până la √n.
Algoritm:
- Dacă n < 2, nu prim
- Dacă n = 2, prim
- Dacă n este par (cu excepția lui 2), nu prim
- Verificați toate numerele impare de la 3 la √n
- Dacă vreunul împarte n egal, nu prim
- În caz contrar, primește
Exemplu: 97 este prim?
√97 ≈ 9,85, deci verificați numerele prime până la 9: 2, 3, 5, 7
- 97 ÷ 2 = 48,5 (nu întreg)
- 97 ÷ 3 = 32,33... (nu întreg)
- 97 ÷ 5 = 19,4 (nu întreg)
- 97 ÷ 7 = 13,86 (nu întreg)
Nu s-au găsit divizori — 97 este prim.
Exemplu: 91 este prim?
√91 ≈ 9,54, verificați până la 9: 2, 3, 5, 7
- 91 ÷ 7 = 13 (număr întreg!)
91 nu este prim — 91 = 7 × 13.
Metoda 2: Sita lui Eratosthenes
Sita lui Eratosthenes găsește toate numerele prime până la o limită dată. Este rapid și elegant, inventat de matematicianul grec Eratostene în jurul anului 240 î.Hr.
Pentru a găsi toate numerele prime până la 50:
- Scrie numerele de la 2 la 50
- Începeți cu 2 (primul prim). Tăiați toți multiplii lui 2 (4, 6, 8...)
- Treceți la următorul număr neîncrucișat: 3. Trimiteți multiplii lui 3 (9, 15, 21...)
- Următorul neîncrucișat: 5. Trimite multiplii lui 5 (25, 35...)
- Următorul neîncrucișat: 7. Trimite multiplii lui 7 (49...)
- Opriți-vă când ajungeți la √50 ≈ 7.07
- Toate numerele rămase neîncrucișate sunt prime
Prime până la 50: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
Prime până la 100: Lista completă
| Gamă | Primele |
|---|---|
| 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 |
Există 25 de numere prime sub 100.
Teste rapide de divizibilitate
Înainte de a face împărțirea completă, verificați aceste reguli:
| Divizibil cu | Dacă... |
|---|---|
| 2 | Ultima cifră este par (0,2,4,6,8) |
| 3 | Suma cifrelor divizibile cu 3 |
| 5 | Ultima cifră este 0 sau 5 |
| 7 | Nicio regulă simplă - doar împărțiți |
| 11 | Sumă alternantă a cifrelor divizibile cu 11 |
Exemplu: 143 este prim?
- Nici măcar ✓
- 1+4+3 = 8, nedivizibil cu 3 ✓
- Nu se termină în 0 sau 5 ✓
- √143 ≈ 11,96, verificați până la 11
- 143 ÷ 7 = 20,43 ✓
- 143 ÷ 11 = 13 — divizibil!
143 = 11 × 13. Nu prim.
De ce contează primele
Criptografie: Criptarea RSA – folosită pentru a securiza internet banking, HTTPS și e-mail – se bazează pe faptul că înmulțirea a două numere prime mari este ușoară, dar factorizarea rezultatului înapoi în numere prime este extrem de dificilă.
Informatica: Tabelele hash, generatoarele de numere aleatoare și sumele de verificare folosesc proprietățile numerelor prime.
Matematică pură: Distribuția numerelor prime rămâne una dintre cele mai profunde probleme nerezolvate din matematică - Ipoteza Riemann.
Fapte principale interesante
- Cel mai mare prim cunoscut (din 2024) are peste 41 de milioane de cifre
- Primele gemene sunt numere prime care diferă cu 2 (11 și 13, 17 și 19, 41 și 43)
- Există infinit de numere prime - dovedite de Euclid în jurul anului 300 î.Hr
- Conjectura lui Goldbach (nedovedită din 1742): fiecare număr par > 2 este suma a două numere prime