[Math] How to find the factors of numbers around 1e7

factoringprime numbersproject euler

I don't have a maths background but I'm solving problems on the awesome Project Euler .net in JavaScript as programming practice.

I don't want to link directly to the question or post it verbatim here because that defeats the point behind working out the puzzles but…

As I think I understand it, all factors of a number can be generated from the prime divisors of that number.

I can generate primes easily for numbers around 1e7 (Code is in JavaScript):

function primes(y) {
    for (var i=2; i<=y; i++) {
        if (y % i === 0) {
            console.log(i);
            y = y/i;
        }
    }
}

What I don't really understand is how I can use those primes to generate all other factors.

Because the question is in regards to a number with more than 500 divisors the brute force approach of (y % i === 0) just won't work.

Please help me with what I'm sure are terrible assumptions.

This is the closest I've come to what I perhaps might need to do but still don't understand the principle behind it.

http://en.wikipedia.org/wiki/Trial_division

Thanks.

Best Answer

You can identify the prime factors of a number $n$ by testing the numbers $2,3,4,\ldots$ to see whether they divide $n$ and exit the loop when you either find a divisor $p$ or reach $\sqrt{n}$ (since if $n=ab$ then either $a$ or $b$ is at most $\sqrt{n}$, so if you reach $\sqrt{n}$ then $n$ is prime). If you find a divisor $p$, repeat this process with $n/p$. In this manner you get all the prime factors of $n$ (don't forget to include the $\sqrt{x}$ you get on your last iteration).

Once you have the prime factors, finding the divisors is easy. Suppose $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$. Then the divisors of $n$ are $p_1^{x_1}p_2^{x_2}\cdots p_k^{x_k}$ where $0\leq x_i\leq e_i$ for all $i\leq k$, thus the number of factors of $n$ is $(e_1+1)(e_2+1)\cdots(e_k+1)$ (as we have $e_i+1$ choices for each $x_i$, and two different choices give us two different divisors since prime factorizations are unique).

Related Question