884 - Factorial Factors

Difficulty : medium

Solution Description :

Prime Number and Prime Factor problem

sqrt(1000000) = 1000
First generate prime number up to 1000. Here exactly 168 prime number
between 1 and 1000
You can calculate number of prime factor using 168 prime number for
any number between 2 to 1000000

Pregenerate all ans up to 1000000 and store all ans to array Ans[1000001]

Set Ans[1]=0
for i=2 to 1000000
----Ans[i] = Ans[i-1] + number of prime factor for i

now input n
print Ans[n]