Algoritmi: Primalitatea unui număr

Un număr prim este un număr natural mai mare ca 1 ce nu are alţi divizori în afară de 1 şi el însuşi. De exemplu: 2 are divizori pe 1 şi 2; 5 are divizorii 1 şi 5; 11 are divizorii 1 şi 11. Acestea sunt numere prime.
Fie \(n\) numărul pe care vrem să-l testăm. În loc să testăm dacă \(n\) are divizori în intervalul \([2, n-1]\), vom testa dacă are divizori în intervalul \([2, \sqrt{n}]\), deoarece un număr neprim are cel puţin un divizor mai mic sau egal cu \(\sqrt{n}\). Implementarea algoritmului în C++:

#include <iostream>
#include <cmath>
using namespace std;

bool estePrim(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;
}

Există totuşi o versiune de 3 ori mai rapidă decât versiunea în care testăm toţi divizorii până la `n-1`. Se observă că aproape toate numerele prime se scriu sub forma `6k +- 1` unde `k` este un număr întreg (Am zis aproape deoarece 2 şi 3 nu sunt de această formă, dar sunt prime, iar pentru `k=4` numărul nu este prim). Aşadar trebuie să testez dacă `n` este 2 sau 3, altfel dacă nu este divizibil cu niciunul din următoarele numere: 2, 3 sau numerele de forma `6k +- 1 <= sqrtn`. Totuşi această metodă nu oferă întotdeauna un rezultat corect. Dacă doriţi mai multe detalii intraţi aici. Implementarea algoritmului în C++:

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int n)
{
    // Daca este 2 sau 3 atunci este prim
    if(n == 2 || n == 3) return true;
    // Daca este divizibil cu 2 sau 3 atunci NU este prim
    if(n % 2 == 0 || n % 3 == 0) return false;
    for(int k = 1; 6*k-1 <= sqrt(n); k++)
    {
        // Daca este divizibil cu 6*k -/+ 1 atunci NU este prim
        if(n % (6*k-1) == 0 || n % (6*k+1) == 0) return false;
    }
    // Daca am ajuns aici, inseamna ca este prim
    return true;
}

Puteţi folosi aceşti algoritmi pentru a genera toate numerele prime până la un anumit număr. De exemplu:

int main()
{
    for(int i = 2; i <= 1000; i++)
        if(isPrime(i))  cout << i << '\n'; 

    system("PAUSE");
    return 0;
}

P.S: Există metode mai rapide de generare a numerelor prime, dar pe care nu le voi prezenta aici.
Mai multe informaţii despre numerele prime aici.