regarding my above answer: the upper limit on the product \Pi should be n. That is, \Pi_{i=1}^n

View Allnum of num

3 Answers

▲

0

▼

regarding my above answer: the upper limit on the product \Pi should be n. That is, \Pi_{i=1}^n

▲

0

▼

your assumption of relatively prime makes the problem easy...i don't think that's the goal...try to answer the actual question without making sweeping assumptions!!

To comment on this, Sign In or Sign Up.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

Your feedback has been sent to the team and we'll look into it.

answer to prime number question: I am assuming that the 2 factors you factorize it into are relatively prime, in that they have no common factors. For a number N, suppose it is represented as a product of prime number N=\Pi_i p_i^(e_i), where p_i is a prime number and e_i represents the number of such primes in N's prime number factorization. For N=xy, we see that for each p_i, we can choose whether ALL p_i factors go to x or go to y (2 choices). it cannot be that we take some of the p_i factors and give them to x, then give the others to y because otherwise x and y will have common factors. Thus, for each p_i we have 2 choices as to where it can go: x or y. So nominally we have 2^n possibilities. However, since (a)(b) and (b)(a) are considered the same factorization, we over count by a factor of 2, so really we have 2^(n-1) possibilities.