Limit on factors in Integer Factorization problem (65)
Back to General discussions forum
Is it correct to suppose that factors of each number does not exceed 1000?
In other words, can every number in task be represented as product x1^p1 * x2^p2 * ... * xn^pn, where x1 < x2 < ... < xn < 1000?
This is an example, but what about actual tests? Did you got tests with factors in test case greater than 1000?
I could make some submissions myself to check it out myself, but unfortunately offended the site too much by getting tests for tasks 251 - 270 yesterday.
Two quick runs seem to suggest that the problem generator only uses prime numbers up to 600,
so comfortably within the 1000 constraint.
Ideally a solution should be able to deal with much larger primes (you only have to check up to sqrt(n)).
Yeah, this is what I thought, thank you.
With this knowledge I can reduce my solution to just one line - great!
Checking up to sqrt(n) is no fun, because then you need to check if number is fully factorized after divisions, like with 6 = 2 * 3, you check for 2 < sqrt(6), but do not check for 3 > sqrt(6) unless you make an extra check.
All you do is a single final check whether the remaining number is 1 or not.
If it is not, then you have one more prime factor (there can only be one greater than sqrt(n)).