daniela a fost fascinata la lectia de matemiatica de numerele prime. Ea a inceput sa aleaga numere din ce in ce mai mari ca sa le verifice daca sunt prime sau nu. Procesul de verificare este,insa,anevoios. Tu cum ai descrie un algoritm care verifica daca un numar este prin sau nu (Limbaj C++ va rog)
Răspunsuri la întrebare
Răspuns:
#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;
}
Explicație:
bool isPrime(int number = 0)
{
if (number <= 1)
return false;
if (number == 2)
return true;
if (number % 2 == 0)
return false;
int divisor = 3;
while (divisor * divisor <= number)
{
if (number % divisor == 0)
return false;
divisor += 2;
}
return true;
}