Cerința

Se dau n numere naturale. Aflaţi pentru fiecare număr câţi factori primi are în descompunere.

Date de intrare

Fișierul de intrare eratostene2.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire eratostene2.out va conține pe prima linie n numere, fiecare reprezentând numărul factorilor primi din descompunerea numărului corespunzător din fişierul de intrare.

Restricții și precizări

• 1 ≤ n ≤ 500.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemplu

eratostene2.in

7
30 5 44 210 1 35 30030

eratostene2.out

3 1 2 4 0 2 6

Explicație

Numerele date se descompun astfel: 30=2•3•5 , 5=5 , 44=22•11 , 210=2•3•5•7, 1=1, 35=5•7 , 30030=2•3•5•7•11•13.

#include <bits/stdc++.h>

using namespace std;

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

int p[500001], P;
bitset<1000000> e;

void eratostene(){
    e[0] = e[1] = 1;
    for(int i = 2; i * i <= 10000; ++i)
        for(int j = i * i; j <= 10000; j += i)
            e[j] = 1;
    for(int i = 1; i <= 10000; ++i)
        if(!e[i])
            p[++P] = i;
}

int desc(int n){
    int d = 1;
    int cnt=0;
    while(n > 1){
        int pi = 0;
        while(n % p[d] == 0)
            n/=p[d], pi++;
        if(pi)
            cnt++;
        d++;
        if(n > 1 && p[d] * p[d] > n){
            cnt++;
            break;
        }
    }
    return cnt;
}

int main(){
    int n;
    eratostene();
    cin >> n;
    for(int i = 1; i <= n; ++i){
        int x;
        cin >> x;
        cout << desc(x) <<' ';
    }
    return 0;
}