un algoritm eficient de primalitate va rog!
Răspunsuri la întrebare
Răspuns:
inceput
natural nr,d
logic prim
citeste nr
prim<--t
cat timp(prim = t si d<= sqrt(nr))executa
daca(nr mod d =0) atunci
prim<--f;
altfel d<--d+1;
}
Cerinta: Algoritm eficient de verificare a primalitatii unui numar
Sa definim cateva notiuni:
- Orice numar mai mic sau egal cu 1 nu este numar prim
- Orice numar par in afara de 2 nu este numar prim
- Primul numar prim este 2
Algoritm in pseudocod pentru verificarea primalitatii:
start
natural n, i
logic ok
ok ← adevarat
citeste n
┌ daca n <= 1, atunci
│ ok ← fals
└■
┌ daca n <> 2 si n % 2 = 0, atunci
│ ok ← fals
└■
┌ daca ok = adevarat, atunci
│ ┌ pentru i ← 3, i * i <= n, executa
│ │ ┌ daca n mod i = 0, atunci
│ │ │ ok ← fals
│ │ └■
│ └■
└■
┌ daca ok = adevarat, atunci
│ scrie "Numarul " n " este numar prim"
└■
┌ altfel
│ scrie "Numarul " n " nu este numar prim"
└■
stop
Transcrierea in C++ ca si functie care returneaza true/false
bool prim(int n) {
if (n <= 1) {
return false;
}
else if (n != 2 && n % 2 == 0) {
return false;
}
for (int i = 3; i * i <= n; i += 2) {
if (n % i == 0) {
return false;
}
}
return true;
}