Cum verifici daca un numar este prim?
Răspunsuri la întrebare
Metoda simpla pentru a determina daca un numar natural n este prim sau compus, recomandat de manualele de matematica (clasa a V-a) este urmatorul :
- Se iau numerele naturale prime mai mici decat n in ordine crescatoare si se pun intr-o lista.
- Se verifica daca numarul pe care il verificam, n se imparte exact (cu rest 0) la aceste numere prime. Ne oprim atunci cand catul devine mai mic sau egal cu impartitorul (caz in care numarul n este prim) sau cand gasim un numar prim la care n se imparte exact (caz in care numarul n nu este prim, ci este compus).
► Numerele prime pana la 200 sunt :
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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199
In documentul atasat ai lista cu numere prime in ordine crescatoare pana la 10000000 care ar trebui sa fie suficienta pentru orice numar cu maxim 14 cifre. Daca vrei sa verifici daca un numar cu 15 cifre este prim imi pare rau, va trebui sa iti cauti alta lista.
► Exemple :
◘ Vrem sa verificam daca n=487 este prim sau compus :
487 : 2 = 243 rest 1
487 : 3 = 162 rest 1
487 : 5 = 97 rest 2
487 : 7 = 69 rest 4
487 : 11 = 44 rest 3
487 : 13 = 37 rest 6
487 : 17 = 28 rest 11
487 : 19 = 25 rest 12
487 : 23 = 21 rest 4
Deoarece am ajuns in punctul in care catul (21) este mai mic sau egal cu impartitorul (23) si nu am obtinut pana aici restul 0 la niciuna dintre impartiri inseamna ca 487 este un numar prim.
◘ Vrem sa verificam daca n=407 este prim sau compus :
407 : 2 = 203 rest 1
407 : 3 = 135 rest 2
407 : 5 = 81 rest 2
407 : 7 = 58 rest 1
407 : 11 = 37 rest 0
Deoarece am obtinut rest 0 la impartirea lui 407 la 11 inseamna ca numarul 407 este compus.
► Vrem sa verificam daca n=1523 este prim sau compus
1523 : 2 = 761 rest 1
1523 : 3 = 507 rest 2
1523 : 5 = 304 rest 3
1523 : 7 = 217 rest 4
1523 : 11 = 138 rest 5
1523 : 13 = 117 rest 2
1523 : 17 = 89 rest 10
1523 : 19 = 80 rest 3
1523 : 23 = 66 rest 5
1523 : 29 = 52 rest 15
1523 : 31 = 49 rest 4
1523 : 37 = 41 rest 6
1523 : 41 = 37 rest 6
Deoarece am ajuns in punctul in care catul (37) este mai mic decat impartitorul (41)
► De retinut :
- Un numar natural care se imparte exact (cu rest 0) la 1 si la el insusi se numeste prim.
- Un numar natural care nu este prim se numeste compus. De retinut este faptul ca 1 si 0 sunt primele numere compuse.
► Avantaje ale acestei metode :
Este usor de folosit, este rapida si fezabila pentru numere foarte mici (de tipul celor pe care le gasesti in exercitii), poate fi folosita manual si isi indeplineste decent rolul didactic.
► Dezavantaje ale acestei metode :
Avem nevoie de un tabel suficient de mare care sa contina numerele prime in ordine crescatoare. Un tabel cu primele 100 de numere prime poate fi folosit cu succes pana la 10000. Tabelul dat de mine mai sus cu numere pana la 200 poate fi folosit cu succes pentru toate numerele mai mici decat 40000. Daca vrem sa verificam daca un numar extrem de mare este prim (asa cum este necesar in practica) aceasta metoda nu este fezabila pentru ca presupune ca avem deja o lista suficient de mare de numere prime cumva, prin magie. In plus, intr-un sistem de demonstratie riguros nu este acceptabil sa avem deja o lista cu numere prime care se presupune ca este corecta si completa.
► Stiai ca....
- Numerele prime sunt foarte importante in algoritmi criptografici care stau la baza securitatii tuturor informatiilor digitale ? Se ofera recompense mari (mii de dolari) pentru cine reuseste sa gaseasca numere prime extrem de mari (cu cateva sute sau mii de cifre).
- Singurul numar par este 2 ?
______________
Daca doresti sa vezi cum ne putem construi lista de numere prime de la 0, asa cum se foloseste in practica pentru numere mari (nu ca la scoala in clasa a V-a) dar si la scoala la disciplina informatica, metoda cu care si matematicienii rigurosi dar si persoane care verifica numere prime colosale ar fi (oarecum) fericiti iti recomand urmatoarea intrebare : #editme