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ât 2.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;
}