„Un număr prim este un număr natural care are exact doi divizori: numărul 1 și numărul în sine. Cel mai mic număr prim este 2, în afară de 2 toate numerele prime sunt numere impare.
Un număr natural p > 1 se numește prim dacă : p | ab atunci p | a sau p | b, unde a, b sunt numere naturale.
De exemplu 15 | 9 * 5, dar 15 | 9, 15 | 5, adică 15 nu este număr prim.
În anul 300 î.Hr. Euclid a demonstrat că există o infinitate de numere prime. Iată demonstrația: presupunând prin absurd că p ar fi cel mai mare număr prim, construim numărul n=2x3x5x……xp+1. Acesta nu se divide cu nici unul din numerele 2, 3, 5, ….., p, așadar sau este prim, sau are un divizor prim mai mare ca p, ceea ce contrazice presupunerea că p ar fi cel mai mare număr prim.
Nu se știe dacă există o infinitate de numere prime gemene (impare consecutive ca: [3, 5]; [41, 43]; [59, 61]; [101, 103] etc.).”
Sursă: Wikipedia
Considerand un numar n putem afla daca acesta este prim sau nu aplicand urmatorul algoritm:
|
Pseudocod Di: n De: mesaj (Da/Nu) Daux: prim, d citeşte n prim←1 d←2 ┌cât timp d<=n/2 execută │ ┌dacă n%d=0 │ │ atunci prim←0 │ └■ │ d←d+1 └■ ┌dacă prim=1 │ atunci scrie "Da" │ altfel scrie "Nu" └■ |
Limbaj C++ #include <iostream.h>
long int n, prim, d;
main()
{
cin>>n;
prim=1;
d=2;
while (d<=n/2)
{if (n%d==0)
prim=0;
d=d+1;
}
if (prim==1)
cout<<"Da";
else cout<<"Nu";
}
|
