Cum ar trebui sa rezolv aceasta problema de pe PbInfo? Am incercat intr-un mod, dar nu mi-a iesit nimic.

#29 MaxPrime
Cerinţa
Să se scrie o funcție C++ care, pentru un număr natural n transmis ca parametru, determină și întoarce prin intermediul unor parametri de ieșire cele mai mari două numere naturale prime mai mici decât n.

Restricţii şi precizări
numele funcției va fi sub
funcția va avea exact trei parametri, în această ordine:
primul pa

Responsive Ad Header

Întrebare

Clasă: Education Materie: informatica
Cum ar trebui sa rezolv aceasta problema de pe PbInfo? Am incercat intr-un mod, dar nu mi-a iesit nimic.

#29 MaxPrime
Cerinţa
Să se scrie o funcție C++ care, pentru un număr natural n transmis ca parametru, determină și întoarce prin intermediul unor parametri de ieșire cele mai mari două numere naturale prime mai mici decât n.

Restricţii şi precizări
numele funcției va fi sub
funcția va avea exact trei parametri, în această ordine:
primul parametru, n, reprezintă un număr natural, 5 ≤ n < 1000000000
a și b sunt parametrii prin care funcția va întoarce cele două valori căutate
parametrii a și b respectă relația a>b

Exemplu
Dacă n=28, apelul subprogramului va furniza prin parametrul a valoarea 23, iar prin b valoarea 19.
Întrebare a fost pusă de:
819 Vezi 500 Răspunsuri

Răspuns (500)

Cel mai bun răspuns
(1286)
void sub(int n, int &a, int &b)
{
    //in vectorul x calculez toate numrele prime pana la n
    vector <bool> x(n+1); 
    int s=sqrt(n),q,k; // metoda de calcul e Sieve of Atkin
    for (int i=1; i<=s; i++)
        for (int j=1; j<=s; j++)
        {
            q=4*i*i+j*j;
            if (q<=n &&(q % 12 ==1 || q % 12 == 5)) x[q]=!x[q];
            q=q-i*i;
            if (q<=n && q % 12 ==7) x[q]=!x[q];
            q=q-2*j*j;
            if (i>j && q<=n && q % 12 ==11) x[q]=!x[q];
        }
    for (int i=1; i<=s; i++)
        if (x[i])
        {
            k=q=i*i;
            while (q<=n)
            {
                x[q]=false;
                q+=k;
            }
        }
    x[2]=x[3]=true;
    // numerele prime deja sunt calculate si ramane doar sa gasim 2 cele mai mari
    int i=n,j;
    for (; ; i--)
        if (x[i])
        {
            a=i;
            j=i-1;
            break;
        }
    for (; ; j--)
        if (x[j])
        {
            b=j;
            break;
        }
}
(752)
void sub(int n, int &a, int &b)
{
    int k = n, nr = 2, i;
    bool prim;
    while(k > 0 && nr > 0)
    {
        k--;
        prim = true;
        for(i = 2; i * i <= k; i ++)
         if(k % i == 0)
         {
             prim = false;
             break;
         }
        if(prim)
        {
            if (nr == 2)
            {
                a = k;
                nr --;
                continue;
            }
            if (nr == 1)
            {
                b = k;
                nr --;
            }
        }
    }
    return;
}