Search This Blog

Thursday, February 16, 2012

C++: Verificarea lui "n" daca este prim (varianta clasica)

Un alt algoritm important, clasic si util este acela ce verifica daca numarul "n" este un prim. Exista mai multe variante ale "for"-ului dupa "d" din aceasta problema si anume limitarea "d<=n", "d<=n/2" sau "d*d<=n", in ordinea descrescatoare timpului de executie (de la cel mai mare la cel mai mic). Algoritmul pe care vi-l voi prezenta este cel mai scurt de scris si cu un timp foarte rezonabil (cel mai rezonabil dintre cele 3 variante) si este si usor de invatat, totusi e bine de stiut ca mai exista si alti algoritmi ce verifica acest lucru, insa sunt mult mai lungi, mai greoi, dar cu un timp de executie remarcabil mai mic.
Iata algoritmul:
                    
                    prim=1;
                    for(i=2; i<=n/2; i++)  ...

                        if(n%i==0) prim=0;
                     if(prim==1)    DA
                     else NU
                     }

Succes la invatat! Sper sa va ajute!