Să se scrie o funcție C++ care verifică dacă un număr natural transmis ca parametru este aproape prim. Un număr natural este aproape prim dacă se poate scrie ca produs de două numere prime distincte.

Restricţii şi precizări

• numele funcției scrise este a_prim
• funcția are un parametru, număr natural, a cărui valoare este mai mică decât 2 ³¹
• rezultatul funcției este 1 dacă valoarea parametrului este aproape prim, respectiv 0 în caz contrar

Exemplu

Numărul 14 este aproape prim, deoarece 14=2*7, iar 2 și 7 sunt numere prime.

Important

Soluția propusa va conține doar funcția cerută. Introducerea în soluție a altor instrucțiuni poate duce la erori de compilare sau de execuție, care vor duce la depunctarea soluției.

bool prim(int n){
    int d = 2, cnt = 1;
    while(n > 1){
        int p = 0;
        while(n % d == 0)
            n/=d, p++;
        d++;
        cnt *= (p + 1);
        if(d * d > n)
            d = n;
    }
    return cnt == 2;
}

bool a_prim(int n){
    int cnt = 0;
    for(int d = 2; d * d <= n; ++d){
        if(n % d == 0)
            cnt+=2;
        if(d * d == n)
            cnt--;
    }
    if(cnt == 2){
        int a, b;
        for(int d = 2; d * d <= n; ++d)
            if(n % d == 0)
                a = d, b = n / d;
        if(prim(a) && prim(b))
            return 1;
    }
    return 0;
}