Lets discuss another problem on codechef of medium difficulty NUMFACT
The problem says you are given n numbers and you have to return the total number of factors of the product of given n numbers.
So the problem consists of two problems:
- Given a number return all the prime factors. If prime factors are known other factors can be calculated.
- Given all prime factors of n numbers, return count of factors of the products of those n number.
Lets first solve 2nd problem
Lets assume we are given 2 numbers 6 and 10, so we need to return count of factors of 10*6 =>60.
6 => 2*3
factors of 60 are:
1(203050), 2(213050), 3(203150), 5(203051), 4(223050), 6(213150), 10(213051), 12(223150), 15(203151), 20(223051), 30(213151), 60(223151)
Now you might have guessed the result. To get the factors of a number we have to choose the coefficient of the prime factors. In case of 1, we chose to not choose any factor, in case of 12, we chose to choose 2 twice and 3 once and not choose 5.
So in how many ways we can do this choosing stuff is the total number of factors. We can do choosing in “product of all factors coefficient’s next number” ways. So for the above example (2+1)(1+1)(1+1)=>(3)(2)(2)=>12 ways
Now lets shift to the first problem. How to determine number of prime factors of a number along with its coefficients.
Since the number given can’t be more than 1000000, we know that it’s factor can be more that 10000001/2 => 1000. That means we just need to check whether numbers less than or equal to 1000 are factors of given number are not. In fact we should just check for prime factors less than or equal to 1000.
To compute prime numbers less than 1000.
- one simple approach would be that for each number(lets say x) less than 1000, start with 2 and check and go till x1/2 and see whether this number divides that number or not. If we get any number till x1/2 which divides x then x is not prime, if we don’t get any number then x is a prime.
- A better approach would be to create an array of 1000 elements(lets name isPrime) all element initialized to true, then start with i =2 and change all its multiple to false. Again start with i=3 and change all its multiple to false, again start with i=4 but since i=4 is already false don’t do any thing for this i and so on….