Here is the problem statement
http://www.spoj.com/problems/PTIME/
Let's have a look at constraints. N<=1000
N!=1*2*3*4*5*6*...*N
We can just loop over numbers from 1 to N and factorize them, then sum the found powers of prime factors and output them in the right order which is. The factorization takes O(sqrt(N)) time. You can find information about prime factorization here.
http://www.spoj.com/problems/PTIME/
Let's have a look at constraints. N<=1000
N!=1*2*3*4*5*6*...*N
We can just loop over numbers from 1 to N and factorize them, then sum the found powers of prime factors and output them in the right order which is. The factorization takes O(sqrt(N)) time. You can find information about prime factorization here.
No comments:
Post a Comment