În ajunul Crăciunului la marele mall din Acropole s-a organizat o tombolă la care au participat n persoane. Acestea au extras pe rând câte un număr, iar câștigători au fost cei care au extras numerele magice. Un număr este magic dacă numărul său de divizori este minim.

Cerința

Câți câștigatori au existat?

Date de intrare

Fişierul de intrare magic3.in conţine pe prima linie variabila n cu indicația din enunț, iar pe a doua linie cele n numere naturale v[1],v[2],...,v[n] , separate prin câte un spațiu, reprezentând numerele extrase la tombolă.

Date de ieșire

Fişierul de ieşire magic3.out conţine o singură valoare care reprezintă numărul de câștigatori.

Restricții și precizări

• 1 ≤ n ≤ 1.000
• 0 < v[i] ≤ 1.000.000.000
• Numerele se pot repeta în această tombolă

Exemplu

magic3.in

8 
12 5 10 7 32 2 4 99

magic3.out

3

Explicație

Numărul minim de divizori este 2. Și avem 3 numere care au doar 2 divizori.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("magic3.in");
ofstream cout("magic3.out");

int nrdiv(int n)
{
    int prod = 1 , d = 2;
    while(n > 1)
    {
        int p = 0;
        while(n%d==0) p++ , n /= d;
        if(p) prod *= (p+1);
        d++;
        if(d*d>n) d = n;
    }
    return prod;
}

int main()
{
    int n , a[1005] , cnt=0 , min = 1000000000;
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)
    {
        cin >> a[i];
        if(nrdiv(a[i]) < min) 
            min = nrdiv(a[i]);
    }
    for(int i = 1 ; i <= n ; ++i)
    {
        if(nrdiv(a[i]) == min)
            cnt++;
    }
    cout << cnt;
    return 0;
}