2
$\begingroup$

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.

  • 0
    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?2012-05-12
  • 0
    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)$.2012-05-12
  • 0
    @AndréNicolas Oops. Perhaps I should have checked the comments before submitting my answer.2012-05-12
  • 1
    @AlexBecker: A comment is only a comment, something off-hand.2012-05-12
  • 0
    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...2012-05-12

1 Answers 1

4

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

  • 0
    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.2012-05-12
  • 0
    @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$.2012-05-12
  • 0
    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.2012-05-12
  • 0
    @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$.2012-05-12
  • 0
    Thanks very much for the explanation. I won't say I completely get it yet but it's enough to go do some more research. I need to go find out why in your last example `n` now = 2 (Is it being re-used? wasn't it 28?). Where does `e` come from? How do you find the exponent of the primes...). So much to learn.2012-05-12
  • 0
    @gyaresu That was a failure of notation. I'll edit the post to make things clearer.2012-05-12
  • 0
    @gyaresu let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/3413/discussion-between-alex-becker-and-gyaresu)2012-05-12
  • 1
    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!2012-05-12