Question

Se citeste un numar natural n . Sa se verifica daca este numar prim . As dori in c++ sau pseudocod.

Answer 1

► Prin definitie, un numar prim este un numar care se imparte exact (cu restul 0) doar la 1 si la el insusi.

Stim ca un numar se poate imparti exact doar la numere mai mici sau egale decat el (este evident ca 5 nu se poate imparti exact la 8, spre exemplu).

◘ Folosind definitia si observatia de mai sus putem realiza urmatorul algoritm simplu, invatat in primul an de studiu al informaticii:

[vezi imaginea 1]

[vezi atasament .cpp pentru abordare C++]

Practic verificam daca exista un numar mai mic decat n la care n se poate imparti exact.

Reamintim ca folosim operatorul % pentru a determina restul impartirii unui numar natural la altul. Daca rezultatul operatiei este 0 atunci primul numar se imparte exact (este divizibil) cu al doilea numar

Algoritmul este foarte simplu, dar ineficient. Daca asta e tot ce iti trebuie poti sa te opresti din a citi raspunsul aici, dar iti recomand sa citesti in continuare.

_________

► Observatie #1: Daca exista un numar natural i la care n se imparte exact atunci n se imparte exact si la n/i. Presupunem ca i<n/i, asta inseamna ca luand numerele la rand il vom gasi mai intai pe i, apoi pe n/i. Dar nu are sens sa il cautam pe n/x deoarece l-am fi gasit deja pe i daca acesta ar fi existat. Daca l-am gasit pe x atunci numarul este prim. Daca nu l-am gasit pe x atunci nu il putem gasi pe n/x.

◘ Care este x maxim ?

$x < \frac{n}{x} \implies x^2 < n \implies x < \sqrt{n}$

Altfel spus nu are sens sa verificam toate numerele mai mici decat n, trebuie sa mergem doar pana la √n (sau pana cand i²>=n, e acelasi lucru matematic dar ridicarea la putere este mai rapida decat calculul radacinii)

Putem optimiza programul astfel :

[vezi imaginea 2]

Nota : Aceasta e motivul pentru care in metoda matematica de verificare daca un numar este prim mergem doar pana cand catul devine mai mic sau egal cu impartitorul. In caz in care vrei sa recapitulezi poti gasi teoria aici: https://brainly.ro/tema/7901390

_________

► Observatie #2: Putem face o verificare suplimentara in program care sa reduca numarul de verificari la jumatate.

• Singurul numar par prim este 2.
• Un numar impar nu se poate imparti exact la un numar par

Putem verifica la inceput daca numarul este par. Daca este par si este 2 atunci numarul e prim. Daca este par si nu este 2 atunci cu siguranta cu e prim.

Astfel nu va fi necesar sa verificam pentru i=4, i=6, i=8, etc. scutind astfel jumatate din numarul de verificari.

Aceasta este solutia implementata de antonii in raspunsul de aici (C++, metoda optimizata) : https://brainly.ro/tema/2764923

__________

► Observatie #3: Presupunem ca exista un i natural astfel incat n se imparte exact la i si i este compus (nu e prim).

Orice numar compus poate fi scris ca produs de numere prime la o putere nenula ($i=a_1^{x1} * a_2^{x2} * .... a_k^{xk}$), unde $a_1 < a_2 < ... < a_k$ . Daca n se imparte exact la i atunci n se imparte exact si la $a_1$, iar $a_1$ este evident mai mic sau egal decat i.

Altfel spus, daca n nu se imparte exact la $a_1$ (un numar natural prim) atunci n nu se va imparti exact la niciunul dintre numerele care in contin pe $a_1$ in descompunerea lor (care sunt mai mari sau egale decat $a_1$). Idem pentru $a_2$, $a_3$,..., $a_k$.

Aceasta observatie este o generalizare a observatiei anterioare.

In concluzie, nu are sens sa verificam daca n se imparte la orice numar natural mai mic sau egal decat √n, ci doar la numerele prime cu aceasta proprietate. Acesta este motivul pentru care in metoda simpla, matematica de verificare (clasa a V-a) luam doar numerele prime. In cazul in care vrei sa reamintesti metoda : https://brainly.ro/tema/7901390

Totusi aceasta observatie este utila doar in cazul in care avem tabelul cu numere prime cu toate valorile prime mai mici sau egale decat √n (pe care prin magie, in clasa a V-a se presupune cumva ca il avem, dar in practica trebuie construit) si nu ne avantajeaza daca dorim sa verificam (folosind un algoritm aplicat pe un sistem de calcul) daca un singur numar este prim sau nu.

Observatia este utila totusi pentru a constui de la 0 (in maniera bottom-up) o lista cu numerele naturale pana la n. Apoi putem face o verificare simpla (folosind cautare binara sau implementand structura ca o tabela de dispersie) daca un numar se afla in lista. Putem astfel genera o singura data tabela (complexitate mare), dar putem verifica rapid daca un numar se afla in ea. Aceasta varianta e extrem de eficienta in practica, mai ales daca trebuie sa verificam daca un numar mare de valori sunt prime.

Ai metoda de constuire de la 0 prezentata in raspunsul de aici (impreuna cu aplicatii) : editme

34fa9eb2f3ff5785cf75031a89ce585d.cpp