Pentru a verifica daca un numar natural n este prim sau nu vom efectua urmatorii pasi :
- Facem rost de o lista cu numere prime in ordine crescatoare cel putin pana la x, unde x este cel mai mic numar al carui patrat este mai mare sau egal cu numarul pe care vrem sa il verificam. ( daca n este numarul de verificat atunci x*x≥n)
- Se ia fiecare numar prim din lista. Incercam sa impartim n la numarul prim curent. Daca se imparte exact (obtinem rest 0) atunci numarul nu e prim (ci este compus). Continuam sa verificam cu fiecare numar prim din lista pana cand catul devine mai mic decat impartitorul. In acest caz ne oprim, iar daca pana acum nu am obtinut restul 0 la una din impartiri atunci numarul este prim
► Exemplu :
◘ Vrem sa verificam daca n=87 este prim sau compus :
Primul numar x cu proprietatea x²≥87 este 9. Numerele prime pana la 9 sunt 2,3,5,7.
87 : 2 = 43 rest 1
87 : 3 = 29 rest 0
Deoarece am obtinut rest 0 ne oprim, inseamna ca 87 nu este prim.
◘ Vrem sa verificam daca n=113 este prim sau compus. Lista de numere prime de care avem nevoie este 2,3,5,7,11.
113 : 2 = 56 rest 1
113 : 3 = 37 rest 2
113 : 5 = 22 rest 3
113 : 7 = 16 rest 1
113 : 11 = 10 rest 3
Am ajuns in punctul in care catul (10) este mai mic decat impartitorul (11), deci ne oprim. Nu am obtinut nicaieri restul 0. Numarul 113 este prim.
________________
Iti recomand sa citesti raspunsul de aici ( https://brainly.ro/tema/7901390 ) pentru mai multe informatii :
- Mai multe exemple
- Teorie explicata mult mai bine
- Informatii suplimentare
- Lista cu toate numerele prime pana la 10000000
