Jump to content

[C++] Verificare numar prim


Krusher
 Share

Recommended Posts

  • Administrator

Acest algoritm face parte din unul dintre algoritmii elementari ce fiecare elev de liceu ar trebui sa-l stie. Acesta verifica daca un numar este prim sau nu, dupa un principiu foarte simplu. Vom parcurge toate numerele de la 2 la (numar / 2 – pentru optimizare) si vom verifica daca acesta se imparte exact la numarul nostru. Putem optimiza algoritmul si mai mult si sa parcurgem numerele pana la radical din numarul respectiv – pentru ca exista o teorema in matematica care ne ajuta.

 

Definitia unui numar prim: Un numar este prim daca acesta se imparte doar la 1 si la el insusi. 

Exemplu: 13.
Observatie: Doar numerele naturale sunt prime, deoarece cele intregi se impart la -1.

This is the hidden content, please

-

Link to comment
Share on other sites

bool numarPrim(int numar)

{
    if(numar < 2) // Daca numarul este mai mic ca si 2 (1, 0, -1, -2, etc) - acesta nu este prim
        return false;
    if(numar == 2) // Daca numarul este 2, acesta este prim
        return true;

    /* optimizare fara a fi nevoie de biblioteca math.h pentru functia sqrt */
    for(int i = 2; i * i <= numar; i++)
        if(numar % i == 0)
            return false;
    return true;
}
 

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...