Probleme de informatică
Clasa a IX-a
Elementele de bază C++ (46)
Subprograme predefinite (1)
Fişiere text (2)
Algoritmi elementari (109)
Tablouri unidimensionale (83)
Tablouri bidimensionale (64)
Probleme diverse (13)
Clasa a X-a
Subprograme (funcții) (87)
Şiruri de caractere (49)
Tipul înregistrare (26)
Recursivitate (57)
Alocarea dinamică a memoriei (2)
Liste înlănţuite (25)
Algoritmul lui Lee (1)
Clasa a XI-a
Metoda "Divide et impera" (12)
Metoda Backtracking (85)
Metoda Greedy (6)
Programare dinamică (18)
Grafuri neorientate (37)
Grafuri orientate (38)
Arbori (33)
Clasa a XII-a
Elemente de bază C# (32)
POO în C# (13)
Programare vizuală în C# (11)
Examen de bacalaureat
Competențe digitale
Examen de atestat
Admitere UBB (18)
Sa se scrie o functie aproape_ prim care primeste ca parametru un numar natural n si returneaza 1 daca n este aproape prim, sau 0 in caz contrar. Spunem ca un numar este aproape prim daca poate fi descompus ca produs de doua numere prime distincte. Se cere un algoritm eficient ca timp de executie.
Exemple de astfel de numere: 21 (=3*7), 77(=7*11), 14(=2*7).

int aproape_prim(int n)
{
    int d=2,k=0;
    while(n>1)
        if(n%d==0)
        {
            k++;
            int e=0;
            while(n%d==0)
            {
                e++;
                n/=d;
            }
            if(e!=1) return 0;//nu are voie sa apara un exponent mai mare decat 1
        }
        else d++;
     if(k==2) return 1;//trebuie exact 2 factori primi
     else return 0;
}

sau (mai eficient)

int prim(int n)//verific numar prim
{
    if(n<2) return 0;
    for(int i=2;i*i<=n;i++)
        if(n%i==0) return 0;
    return 1;
}

int a_prim(int n)
{
    int d=2;
    while(n%d!=0 && d*d<n) d++; //caut primul divizor
    if(n%d!=0) return 0;
    if(prim(n/d) && d!=n/d) return 1; //daca n/d este si el prim si n!=n/d
    else return 0;
}

13 nov 2018
Site-ul conține 868 de probleme rezolvate
Copyright © 2009-2018 Muresan Vasile Ciprian