[C++] Suma Numerelor Prime

[Andreigl]

Un număr prim este un număr care nu se împarte la nici un alt numar, cu excepția cifrei 1 și el însuși. Deci ce putem deduce din asta? 

 

Un număr prim:

• trebuie să aibă obligatoriu 2 divizori.
• nu se împarte niciodată la 2, deci nu este număr par.
• nu este mai mic decât 2, deci un număr negativ nu poate fi număr prim.
• singurul număr par care este număr prim, este cifra 2.

 

Cel mai simplu algoritm pentru a afla dacă un numar este sau nu prim:

int main()
{
    int N;
    cin >> N;

    bool Prim = true;

    for (int i=2; i<N; i++)
        if (N % i == 0)
            Prim = false;

    if (Prim)
        cout << "Este Prim";
    else cout << "Nu este prim";
}

 

Însă, aceasta poate fi optimizată în felul următor:

int main()
{
    int N;
    cin >> N;

    // bool este o variabila booleana care poate fi ori adevarata, ori falsa
    // presupunem ca numarul nostru este un numar prim
    bool Prim = true;

    // incepem de la 2 pana la patratul contorului
    // aceasta functie verifica fiecare numar din intervalul [2, sqrt(N)]
    for (int i=2; (i*i)<=N; i++)
    {
        if (N % i == 0)
            Prim = false;
    }

    // in cazul in care conditia din bula nu a fost indeplinita, atunci numarul nostru este prim
    if (Prim)
        cout << "Este prim";
    else cout << "Nu este prim";
}

 

 

Acum că știm să aflăm dacă un număr este sau nu prim, mai rămâne să facem un program care ne arată suma tuturor numerelor prime pana la N.

Cea mai simplă metodă, însă foarte slabă, mai ales pentru numerele foarte mari, ocupând chiar și de 200 de ori mai mult timp decât varianta optimizată, este următoarea funcție:

 

int main()
{
    int N,
        Suma = 0;

    cin >> N;

    // Vom declara variabila booleana in afara bulei
    bool Prime;

    cout << "Numerele prime sunt: ";

    // Cum 1 nu este numar prim, vom incepe direct de la 2
    for (int i=2; i<=N; i++)
    {
        Prime = true; // Consideram ca i este un numar prim

        // Aici obligatoriu trebuie ca variabila j sa fie mai mica decat i
        // De ce?
        // Sa zicem ca i = 15, daca j ajunge la 15, atunci 15:15 = 1 ==> variabila booleana va fi falsa
        // Stim ca un numar prim are voie sa se imparte chiar si la el insusi, dar el nu trebuie sa se imparta la numerele din intervalul [2,N-1]
        for (int j=2; j<i; j++)
            if (i % j == 0)
                Prime = false;

        // Daca i este prim, atunci il vom afisa si aduna in acelasi timp
        if (Prime)
        {
            cout << i << " ";
            Suma += i;
        }
    }

    cout << "\nSuma numerelor prime este: " << Suma;
}

 

Cu această funcție mi-a luat 5,11 secunde să calculez numerele prime până la 50,000.

 

Varianta optimizată a acestei funcții este puțin mai delicată:

 

#include <iostream>

using namespace std;

int PrimeVerif(int X);

int main()
{
    int N,
        Suma = 0;

    cin >> N;

    cout << "Numerele prime sunt: ";

    for (int i=1; i<=N; i++)
    {
        // Apelam functia ce verifica daca numarul este sau nu prim
        if (PrimeVerif(i))
        {
            cout << i << " ";
            Suma += i;
        }
    }

    cout << "\nSuma numerelor prime este: " << Suma;
}

int PrimeVerif(int X)
{
    // X este singurul numar par care este prim
    if (X == 2)
        return true;

    // 1 sau numerele negative, cat si cele pare, nu sunt prime
    if (X < 2 || X % 2 == 0)
        return false;

    // deoarece am eliminat din start faptul ca nu este numar par (deci nu se imparte la 2), vom verifica doar numerele impare cu o incrementare din 2 in 2
    // obligatoriu trebuie sa punem patratul contorului mai mic sau egal decat X pentru a scapa de patratele perfecte
    for (int i=3; (i*i)<=X; i+=2)
    {
        if (X % i == 0)
            return false;
    }

    // dupa ce bula de sus a fost terminata, iar daca functia noastra ajunge sa citeasca aceasta linie, inseamna ca numarul nostru este numar prim
    return true;
}

 

Cu această funcție, calculul numerelor prime până la 50,000 a durat 1,5 secunde. A fost de aproximativ 3 ori mai rapidă decât funcția de mai sus.

Edited January 18, 2020 by shanker'

[Jackson Brooklyn]

Topic inactiv