Factorialul unui număr natural nenul n, notat n!, se defineşte ca fiind produsul numerelor naturale de la 1 la n. Una dintre modalităţile de reprezentare a factorialului este prin enumerarea factorilor primi pe care îi conţine şi a exponenţilor acestora.

Cerința

Fiind dat un număr natural n, scrieţi un program care determină suma exponenţilor factorilor primi corespunzători descompunerii în factori primi a lui n factorial.

Date de intrare

Fişierul de intrare factorial3.in conţine pe prima linie numărul natural n.

Date de ieșire

Fişierul de ieşire factorial3.out va conţine pe prima linie un număr reprezentând suma exponenţilor numerelor prime din descompunerea în factori primi a lui n!.

Restricții și precizări

• 2 ≤ n ≤ 100000

Exemplu

factorial3.in

5

factorial3.out

5

Explicație

5! = 1*2*3*4*5 = 23 * 31 * 51
3+1+1=5

#include <bits/stdc++.h>
using namespace std;
ifstream cin("factorial3.in");
ofstream cout("factorial3.out");
int main()
{
    int n , s = 0 , f[100005]={0};
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)
    {
        int d = 2 , x=i;
        while(x > 1)
        {
            int p = 0;
            while(x%d==0) p++, x/=d;
            if(p) f[d]+=p;
            d++;
            if(d*d>x) d=x;
        }
    }
    for(int i = 1 ; i <=n ; ++i)
        s+=f[i];
    cout << s;
}