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.