Acest algoritm face parte din unul dintre algoritmii elementari ce fiecare elev de liceu ar trebui sa-l stie. Acesta verifica daca un numar este prim sau nu, dupa un principiu foarte simplu. Vom parcurge toate numerele de la 2 la (numar / 2 – pentru optimizare) si vom verifica daca acesta se imparte exact la numarul nostru. Putem optimiza algoritmul si mai mult si sa parcurgem numerele pana la radical din numarul respectiv – pentru ca exista o teorema in matematica care ne ajuta.
Definitia unui numar prim: Un numar este prim daca acesta se imparte doar la 1 si la el insusi.
Exemplu: 13. Observatie: Doar numerele naturale sunt prime, deoarece cele intregi se impart la -1.
[Protected content]