👤
ALEXANDERROZE
a fost răspuns

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

Răspuns :

LOZANALEXZE
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 [tex] \sqrt{n} [/tex]
EXPRESSZE
#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;
}
Vă mulțumim pentru vizita pe site-ul nostru dedicat Informatică. Ne dorim ca informațiile furnizate să vă fi fost utile. Dacă aveți întrebări sau aveți nevoie de suport suplimentar, nu ezitați să ne contactați. Revenirea dumneavoastră ne bucură, iar pentru acces rapid, adăugați-ne la favorite!


Ze Lesson: Alte intrebari