249
Cerința
Se dau n
numere naturale. Determinați cel mai mic număr care are un singur factor prim. Dacă nu există niciun număr cu un singur factor prim se va afișa mesajul NU EXISTA
.
Date de intrare
Programul citește de la tastatură numărul n
, iar apoi n
numere naturale.
Date de ieșire
Programul va afișa pe ecran numărul cerut.
Restricții și precizări
1 ≤ n ≤ 1000
- cele
n
numere citite vor fi mai mici decât1.000.000.000
Exemplu
Intrare
5 12 9 16 4 20
Ieșire
4
Explicație
Dintre numere citite au un factor prim numerele 9 16 4
. Dintre acestea cel mai mic este 4
.
#include <bits/stdc++.h> using namespace std; bool ok(int n){ int d = 2, cnt = 0; while(n > 1){ int p = 0; while(n % d == 0) n/=d, p++; if(p) cnt++; d++; if(d * d > n) d = n; } return cnt == 1; } int main(){ int n, x, mini = 1000000000; cin >> n; for(int i = 1; i <= n; ++i){ cin >> x; if(ok(x) && x < mini) mini = x; } if(mini < 1000000000) cout << mini; else cout << "NU EXISTA"; return 0; }
Comentarii