Algoritm verificare numar prim C++

Algoritm verificare daca un numar e prim C++

• Ce este si ce face acest algoritm?

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.

Daca doriti sa cititi mai multe despre numrele prime, va las aici un link de pe wikipedia: click.

• Algoritmul pentru verificare unui numar prim

#include <iostream>

using namespace std;

bool numarPrim(int numar) // Functia returneaza doar true sau false - pentru ca nu avem nevoie de alte valori
{
    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;
    // for(int i = 2; i <= sqrt(numar); i++) - Optimizare in caz de nevoie
    for(int i = 2; i <= numar / 2; i++) // Parcurgem toate numerele de la 2 la numar / 2
        if(numar % i == 0) // Daca acesta se imparte exact la acel numar, inseamna ca nu este prim
            return false;
    return true;
}

int main()
{
    int nr;
    cin >> nr;
    if(numarPrim(nr) == true)
        cout << "Numarul este prim";
    else
        cout << "Numarul NU este prim";
    return 0;
}

• Algoritmul pentru verificare unui numar prim recursiv

bool ePrimRecursiv(int div, int n) {
    if(n == 2)
        return true;
    if(n % div == 0 || n == 1)
        return false;
    if(div * div > n)
        return true;
    if(div == 2)
        return ePrimRecursiv(3, n);
    return ePrimRecursiv(div + 2, n);
}