precomputations.
There is a formula for a sum of divisors of a number. if the prime factorization of a number is p1^a1*p2^a2*...*pn^an then the sum of all divisors of the number will be (1+p1+p1^2+...+p1^a1)*(1+p2+p2^2+...+p2^a2)*...*(1+pn+pn^2+..+pn^an)
We need to calculate all the abundant number before processing the input. Factorization takes sqrt time , but before that we better find primes which will fasten up the process of factorization. We find the primes with the sieve of Eratsotenes (for more info about the sieve visit the "Algorithms" ) section of this blog.
There is a formula for a sum of divisors of a number. if the prime factorization of a number is p1^a1*p2^a2*...*pn^an then the sum of all divisors of the number will be (1+p1+p1^2+...+p1^a1)*(1+p2+p2^2+...+p2^a2)*...*(1+pn+pn^2+..+pn^an)
We need to calculate all the abundant number before processing the input. Factorization takes sqrt time , but before that we better find primes which will fasten up the process of factorization. We find the primes with the sieve of Eratsotenes (for more info about the sieve visit the "Algorithms" ) section of this blog.
No comments:
Post a Comment