„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";
}
|
Poti face o mica optimizare in cazul in care ai de verificat un numar foarte mare: verifici divizorii pana la radical din numar. Fiindca radicalul este o operatie destul de costisitoare, cea mai eficienta abordare ar fi:
while (d * d <= n){
if (n%d==0)
…
}
Faceam si eu chestii din astea printr-a 9-a.
Insa astea n-or sa iti aduca vizite.
Borlandc este si invechit.
Te sfatuiesc sa folosesc codblox.
Si daca esti in ubuntu compilatorul de acolo gcc sau g++.
Merci de sfaturi! Scopul acestor articole nu e sa-mi aduca multi vizitatori ci sa ajute in special elevii (cum ai spus si tu de nivelul clasei a 9-a) in rezolvarea unor probleme.
Acum am inteles de ce mi-ai zis ca iti plac algoritmii. M-am cam mirat eu la inceput, dar acum inteleg. Felicitari …
Multumesc! Va mai astept pe aici!
Mergea la cat timp acolo si o alta conditie c
ât timp (d<=n/2)&& (prim←1)
execută
Deoarece dupa cum l-ai scris tu , el chiar daca descopera un divizor propriu ,tot ii mai cauta si pe ceilalti in loc sa arate direct ca e prim !
Se putea mult mai bine…dar voi nu intelegi ca-i pentru liceu…cel mai simplu bagi un „break” in cazu in care restu impartirii are restu 0.
Si nu e nevoie de variabila prim,ocupa spatiu si timp degeaba.
Testezi dak „d” este egal cu n/2.
In caz contrar inseamna ca „d” nu ajuns la n/2 din cauza faptului ca demonstrat faptul ca numarul Nu este prim si acel „break” la scos din functie.
pardon testezi dak „d” este egal cu n/2+1..atunci cand iesi din While ultima comanda e d++ :P
int x,i=2;
cout<>x;
cout<<"Ati introdus numarul : "<<x<<"n";
while(i<=(x/2))
{if(x%i!=0)
i++;
else
cout<<"Numarul introdus Nu este Primn"; break;
}
if(i==(x/2+1)) cout<<"Numarul introdus este numar Prim n";
poti sa incerci acest algoritm:
#include
#include
using namespace std;
int main()
{
int n; // Numarul de testat pentru a se vedea daca este prim.
int i; // Contorul de cicluri.
int is_prime; // Indicator Boolean.
// Presupune ca un numar este prim pana la proba contrarie.
is_prime = true;
// Obtine un numar de la tastatura.
cout <>n;
// Se verifica daca numarul este prim sau nu, testand divizibilitatea cu toate numerele intregi cuprinse intre 2 si sqrt (n).
i = 2;
while(i <= sqrt(static_cast(n)))
{
// Cat timp este mai mic sau egal cu sqrt(n).
if (n%i==0) // Daca n se imparte exact la i.
is_prime=false; // n nu este prim.
i++; // Adauga 1 la i.
}
// Listeaza rezultatul.
if(is_prime)
cout <<"Numarul este prim.";
else
cout <<"Numarul nu este prim";
return 0;
}
#include
#include
using namespace std;
int main()
{
int n;
int i;
int is_prime;
is_prime = true;
cout <>n
i = 2;
while(i <= sqrt(static_cast(n)))
{
if (n%i==0)
is_prime=false;
i++;
}
if(is_prime)
cout <<"Numarul este prim.";
else
cout <<"Numarul nu este prim";
return 0;
}
#include
#include
void main()
{
int n,j,OK=1;
clrscr();
cout<>n;
for(j=2;j<=n/2;j++)
{
if(n%j==0)
OK=0;
else
OK=1;
}
if(OK==1)
cout<<"Da.";
else
cout<<"Nu.";
getch();
}
compilari esuate la toata lumea Am intrat accidental dar vad ca pierd vremea si nu invat nimik si nu stau sa desfac greselile
Îmi pare rău că nu a funcționat. La mine a mers.