Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
@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 1

up vote 4 down vote accepted

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

share|improve this answer
    
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
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! –  gyaresu May 12 '12 at 8:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.