Question

Imi puteti scrie cel mai eficient algoritm de verificare daca un nr. este prim sau nu ? C++ va rog . Multumesc anticipat !

Answer 1

Pentru a afla daca un numar e prim exista algoritmul:

#include <cmath>
bool prime(int x)
{
    int c=0,s=sqrt(x);
    for (int i=2; i<=s; i++)
        if (x % i == 0) c++;
    return (!c);
}

Cu complexitatea temporala $\sqrt{n}$

Answer 2

#include <iostream>
using namespace std;
int n,i;
bool prim;
int main()
{
    cin >> n;
    prim=true;
    if(n == 0 || n == 1) prim = false;
    for(i=2;i*i<=n;i++)
     if(n%i==0)
      {
          prim=false;
          break;
      }
    if(prim) cout << "numarul este prim";
        else cout << "numarul nu este prim";
    return 0;
}