277
Cerinţa
Să se scrie un program care citește un șir de n
numere naturale şi determină numărul din şir care are număr maxim de factori primi.
Date de intrare
Programul citește de la tastatură numărul n
, iar apoi n
numere naturale nenule, separate prin spaţii.
Date de ieşire
Programul afișează pe ecran numărul x
, numărul din şir cu număr maxim de factori primi.
Restricţii şi precizări
0 < n < 1001
- cele
n
numere citite vor fi mai mici decât2.000.000.000
- dacă în şir există mai multe numere cu număr maxim de factori primi, se va afişa cel mai mic dintre acestea
Exemplu
Intrare
5 72 30 12 75 17
Ieșire
30
Explicație
30
are trei factori primi. Celelalte numere au mai puţini factori primi.
#include <bits/stdc++.h> using namespace std; int main() { int n, rez = 0, nrmax = 0; cin >> n; for(int i = 1; i <= n; ++i){ int x; cin >> x; int cx = x; int cnt = 0; int d = 2; while(x > 1){ int p = 0; while(x % d == 0) p ++, x /= d; if(p) cnt++; d++; if(d * d > x) d = x; } if(cnt > nrmax) nrmax = cnt, rez = cx; else if(cnt == nrmax && cx < rez) rez = cx; } cout << rez; return 0; }
Comentarii