Algoritmi: Generarea Numerelor Prime

Metoda Clasică

Metoda clasică de generare a numerelor prime până la o anumită limită presupune iterarea până la acea limită şi verificarea primalităţii fiecărui număr. Dacă este prim atunci va fi afişat pe ecran. Algoritmul în C++:

bool IsPrime(int n)
{
    for(int i = 2; i <= sqrt(n); i++)
        // Daca i divide n, atunci n nu este prim
        if(n % i == 0) return false;
    // Daca am ajuns aici inseamna ca n este prim
    return true;
}

void MetodaClasica(int lim)
{
    cout << 2 << ' ' << 3 << ' ';
    for(int i = 5; i <= lim; i+=2)
        if(IsPrime(i)) cout << i << ' ';
    cout << '\n';
}

Observaţi că sar peste numerele pare (i+=2) deoarece singurul număr par prim este 2. Acest algoritm generează toate numerele prime până la lim. Totuşi există metode mai bune de generare a numerelor prime, iar una din ele este Ciurul lui Eratostene.

Ciurul lui Eratostene

Ciurul lui Eratostene (Sieve of Eratosthenes) este un algoritm de găsire a tuturor numerelor prime până la un număr dat. De data aceasta voi număra numerele prime. Paşii algoritmului:

1. Se iterează de la 2 până la sqrt(lim).
2. Fie p, primul număr prim găsit.
3. Toţi multiplii numărului p*p se marchează ca fiind compuşi (adică ne-primi).
4. În final se numără sau se afişează toate numerele prime din intervalul [sqrt(lim)+1, lim].

Algoritmul în C++:

void Eratostene(int lim) 
{
    int sqr = (int)sqrt(lim); 
    // Variabila in care numar numerele prime
    int nr = 0; 
    // Marcarea numerelor prime se face in acest vector
    bool * isComposite = new bool[lim+1]; 
    // Initial toate sunt prime
    memset(isComposite, 0, sizeof(bool)*(lim+1));
    for(int p = 2; p <= sqr; p++)
    {
        // Daca nu este compus, adica este prim
        if(!isComposite[p])
        {
            ++nr;
            // Marcheaza toti multiplii p*p ca fiind compusi
            for(int k = p*p; k <= lim; k+=p)
            isComposite[k] = true;
        }
    }
    // Numara numerele prime ramase
    for(int i = sqr+1; i <= lim; i++)
        if(!isComposite[i]) ++nr;
    cout << nr << '\n';
    delete[] isComposite;
}

Pentru mai multe detalii intraţi pe Wikipedia.

Ciurul lui Atkin

Ciurul lui Atkin (Sieve of Atkin) este un algoritm rapid şi modern de găsire a tuturor numerelor prime până la un număr întreg. A fost creat de A.O.L. Atkin şi Daniel J. Bernstein. Vă ofer doar implementarea algoritmului în C++, nu şi explicaţia:

void Atkin(int lim)
{
    double sqr = sqrt(lim); int n, nr = 2;
    bool * isPrime = new bool[lim+1];
    // Initial toate numerele sunt neprime
    memset(isPrime, 0, sizeof(bool)*(lim+1));
    for(int x = 1; x <= sqr; x++)
    {
        for(int y = 1; y <= sqr; y++)
        {
            n = 4 * x * x + y * y;
            if(n <= lim && (n % 12 == 1 || n % 12 == 5))
                isPrime[n] = !isPrime[n];
            n = 3 * x * x + y * y;
            if(n <= lim && n % 12 == 7)
                isPrime[n] = !isPrime[n];
            n = 3 * x * x - y * y;
            if(x > y && n <= lim && n % 12 == 11)
                isPrime[n] = !isPrime[n];
        }
    }
    for(int i = 5; i <= sqr; i+=2) 
    {
        // Daca este prim, marcheaza toti multiplii i*i ca fiind neprimi
        if(isPrime[i])
        {
            for(int k = i*i; k <= lim; k+=i*i)
            isPrime[k] = false;
        }
    }
    // Numara numerele prime
    for(int i = 5; i <= lim; i+=2)
        if(isPrime[i]) ++nr;
    cout << nr << '\n';
    delete[] isPrime;
}

Descrierea completă a algoritmului o găsiţi aici.