Divizibilitate / Numere prime


Editat de Candale Silviu (silviu) la data 2015-08-16
Etichete: nicio etichetă

Definiție: Un număr natural este prim dacă și numai dacă are doi divizori diferiți.

Observații:

  • cei doi divizori sunt 1 și însuși numărul;
  • conform definiției, numerele 0 și 1 nu sunt numere prime;
  • un număr care are mai mult de doi divizori se numește compus.

Cum verificăm algoritmic dacă un număr natural n este prim?

  • presupunem că numărul este prim;
  • verificăm cazurile particulare; dacă n este 0 sau 1, schimbăm presupunerea
  • căutăm un divizor în intervalul \( [2 , \sqrt{n}] \), parcurgând numerele din interval
    • dacă îl găsim, schimbăm presupunerea

Observație: Deoarece divizorii unui număr n sunt în pereche, dacă nu găsim divizor în intervalul \( [2 , \sqrt{n}] \), nu vom găsi nici în intervalul \( [\sqrt{n} , n) \).

Program C++:

#include <iostream>
int main()
{
    int n;
    std :: cin >> n;
    bool prim = true; // presupunem ca n este prim
    if(n < 2)
        prim = false; // 0 si 1 nu sunt prime
    for(int d =2 ; d * d <= n ; d ++)
        if(n % d == 0)
            prim = false;
    if(prim)
        std :: cout << n << " este prim";
    else
        std :: cout << n << " nu este prim";
    return 0;
}

Fișiere atașate


Vezi și:

Editat de Candale Silviu (silviu) la data 2015-08-16