CareerCup

Probably can be solved with Dynamic Programming:

num_factors(n) = num_factors(n-1) + ( powers of prime numbers for factors of n = PF(n) )

NF(2) = 1
NF(3) = 1
NF(4) = 3 = NF(3) + 2 note PF(4) = 2 since 4 =2*2

Now note when you are calculating NF(n) if you can factorize n as p*q.
NF(n) = NF(p) + NF(q) since p,q != 1 and < n you have calculated NF(p) and
NF(q) already... :)

algorithm

(1) iterate from 2 to sqrt(n), select only primes between this
(2) try to get as more multiple as possible from n from this prime
(3) ex: n=6125, then get try 2,3 no use try 5: get 5*5*5 and then 7*7
(4) total count gives you the answer

it can be solved using a greedy approach, so no dynamic programming needed...

int factor(int number)
{
number = number > 0 ? number : -1*number;
int factor = 2;
int total = 0;
while(number > 1)
{
while(number%factor==0) {
//printf("%d, ", factor);
total++;
number/=factor;
}
factor++;
}

//printf("\n");
return total;
}

void factorial_factor(int number)
{
number = number > 0 ? number : -1*number;
int total = 0;
for(int i = number; i > 1; i--) {
total += factor(i);
}
printf("total = %d\n", total);
}

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
vector<ll> primes;
vector<bool>isprime(1000011,true);
void seive()
{
ll i,j;
for(i=2; i<=1000010; i++)
{
if(isprime[i])
{
primes.push_back(i);
for(j=i*i; j<=1000010; j+=i)
{
isprime[j]=false;
}
}
}
// for(auto u: primes) cout<<u<<" ";
}
int main()
{
seive();
ll n;
string s;
while(1)
{
getline(cin,s);
if(s=="") break;
n=stoll(s);
ll temp,sum,i,j;
//cin>>n;
//if(n=='\0') break;
temp=n;
sum=0;
for(i=0; primes[i]<=n; i++)
{
while(n>0)
{
sum+=n/primes[i];
n=n/primes[i];
}
n=temp;
}
cout<<sum<<endl;
}
return 0;
}