# How to find the factors of numbers around 1e7?

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.

-
Your question is not clear. Is it that you know the prime factors of $n$, and you want to know how to get the other factors? or is it that you want to know how to get the prime factors of $n$ in the first place? – Gerry Myerson May 12 '12 at 6:21
Success in Project Euler problems involves good use of relevant mathematics, and usually very clever programming, with the emphasis on the latter. I am not sure what you are asking. If you know the prime power factorization $n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ of $n$, you can get all factors of $n$ by multiplying together $0$ to $a_1$ $p_1$'s with $0$ to $a_2$ $p_2$'s, and so on. The total number of factors is $(a_1+1)(a_2+1)\cdots(a_k+1)$. – André Nicolas May 12 '12 at 6:22
@AndréNicolas Oops. Perhaps I should have checked the comments before submitting my answer. – Alex Becker May 12 '12 at 6:25
@AlexBecker: A comment is only a comment, something off-hand. – André Nicolas May 12 '12 at 6:28
The script above does indeed generate all the primes for a number. I do wish to calculate the other factors of the number. Thanks for the help so far, I'm reading... – gyaresu May 12 '12 at 6:44

## 1 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).

-
I'm sorry I follow the first paragraph but I don't understand the where you get e & x from. So the prime factors of 28 are 2 & 7... Nope, I've no idea what to do. Perhaps a link in the faq to mathematical notation would help. – gyaresu May 12 '12 at 6:48
@gyaresu Yes, but you have to count them. It is important to keep track of how many times $2$ divides $28$--in this case it divides $28$ two times, so $28=2^2\times 7^1$ and there are $(2+1)(1+1)=6$ divisors, namely $1,2,4,7,14,28$. – Alex Becker May 12 '12 at 6:52
Thank you Alex. I hope this isn't annoyingly simplistic for you to expand on but :) ... two divides 28 two times? Also, where does (2+1)(1+1) come from. Sorry for such obvious ignorance. – gyaresu May 12 '12 at 7:04
@gyaresu There are $(e_1+1)(e_2+1)\cdots(e_n+1)$ prime factors of $p_1^{e_1}p_2^{e_2}\cdots p_n^{e_n}$. In this case, $n=2,p_1=2,p_2=7,e_1=2,e_2=1$ so we get $6$. – Alex Becker May 12 '12 at 7:13
HUGE shout out to Alex Becker for spending half an hour in chat successfully explaining all of this to me. I really really appreciate the effort! – gyaresu May 12 '12 at 8:17