13
$\begingroup$

This question already has an answer here:

I'm trying to use a program to find the largest prime factor of 600851475143. This is for Project Euler here: http://projecteuler.net/problem=3

I first attempted this with the code that goes through every number up to 600851475143, tests its divisibility, and adds it to an array of prime factors, printing out the largest.

This is great for small numbers, but for large numbers it would take a VERY long time (and a lot of memory).

Now I took university calculus a while ago, but I'm pretty rusty and haven't kept up on my math since.

I don't want a straight up answer, but I'd like to be pointed toward resources or told what I need to learn to implement some of the algorithms I've seen around in my program.

$\endgroup$

marked as duplicate by Douglas S. Stones, vadim123, Jyrki Lahtonen, vonbrand, Julian Kuelshammer May 12 '13 at 18:22

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I don't want a straight up answer. I want to learn and understand how to do this. $\endgroup$ – Senjai May 12 '13 at 17:58
  • 1
    $\begingroup$ General warning for @DouglasS.Stones link: It contains a spoiler on PE#3. $\endgroup$ – apnorton May 12 '13 at 18:00
  • 2
    $\begingroup$ For many of the Euler problems, it is helpful to have a list of prime numbers. A useful way to generate that is the [Sieve of Eratosthenes (en.wikipedia.org/wiki/Sieve_of_Eratosthenes) and save it to a file. $\endgroup$ – Ross Millikan May 12 '13 at 18:17
  • $\begingroup$ @RossMillikan, I was reading about this algorithm and it was written that Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n) so, I think its not memory efficient at all. $\endgroup$ – CodeYogi Sep 18 '15 at 5:07
  • $\begingroup$ @CodeYogi: If you want the primes up to 1 or 10 million, which is what I used, that is not much memory these days. I had no trouble with it in Python. $\endgroup$ – Ross Millikan Sep 18 '15 at 13:42
30
$\begingroup$

The thing with Project Euler is that there is usually an obvious brute-force method to do the problem, which will take just about forever. As the questions become more difficult, you will need to implement clever solutions.

One way you can solve this problem is to use a loop that always finds the smallest (positive integer) factor of a number. When the smallest factor of a number is that number, then you've found the greatest prime factor!

Detailed Algorithm description:

You can do this by keeping three variables:

  • The number you are trying to factor (A)
  • A current divisor store (B)
  • A largest divisor store (C)

Initially, let (A) be the number you are interested in - in this case, it is 600851475143. Then let (B) be 2. Have a conditional that checks if (A) is divisible by (B). If it is divisible, divide (A) by (B), reset (B) to 2, and go back to checking if (A) is divisible by (B). Else, if (A) is not divisible by (B), increment (B) by +1 and then check if (A) is divisible by (B). Run the loop until (A) is 1. The (3) you return will be the largest prime divisor of 600851475143.

There are numerous ways you could make this more effective - instead of incrementing to the next integer, you could increment to the next necessarily prime integer, and instead of keeping a largest divisor store, you could just return the current number when its only divisor is itself. However, the algorithm I described above will run in seconds regardless.

You said you don't want a straight up answer. Regardless, if you want to see one implementation of it, I've uploaded my code for this problem on Pastebin: here (C) and here (Python).


Example: Let's find the largest prime factor of 105 using the method described above.

Let (A) = 105. (B) = 2 (we always start with 2), and we don't have a value for (C) yet.

Is (A) divisible by (B)? No. Increment (B) by +1: (B) = 3. Is Is (A) divisible by (B)? Yes. (105/3 = 35). The largest divisor found so far is 3. Let (C) = 3. Update (A) = 35. Reset (B) = 2.

Now, is (A) divisible by (B)? No. Increment (B) by +1: (B) = 3. Is (A) divisible by (B)? No. Increment (B) by +1: (B) = 4. Is (A) divisible by (B)? No. Increment (B) by +1: (B) = 5. Is (A) divisible by (B)? Yes. (35/5 = 7). The largest divisor we found previously is stored in (C). (C) is currently 3. 5 is larger than 3, so we update (C) = 5. We update (A)=7. We reset (B)=2.

Then we repeat the process for (A), but we will just keep incrementing (B) until (B)=(A), because 7 is prime and has no divisors other than itself and 1. (We could already stop when (B)>((A)/2), as you cannot have integer divisors greater than half of a number - the smallest possible divisor (other than 1) of any number is 2!)

So at that point we return (A) = 7.

Try doing a few of these by hand, and you'll get the hang of the idea. Or just play with the code I've provided. Insert some print statements, see how it iterates through the numbers.

$\endgroup$
  • $\begingroup$ wonderful xisk, thanks for your input. I think my fundemental understanding of prime factors is shaky. I dont understand why you divide the number out when you find it. $\endgroup$ – Senjai May 12 '13 at 19:24
  • $\begingroup$ @Senjai Edit: this is hard to do in the comment space. I'll amend the answer to include an example. $\endgroup$ – xisk May 12 '13 at 19:39
  • $\begingroup$ Thanks for all your help xisk, that makes a lot more sense now. $\endgroup$ – Senjai May 12 '13 at 20:30
  • $\begingroup$ You don't really need to reset (B) to 2 every time. Instead, you can avoid incrementing (B) after you find a prime factor. $\endgroup$ – Arulx Z Nov 9 '15 at 16:22
  • 1
    $\begingroup$ I too am confused about resetting B to 2 every time. I concur with the previous comment - I feel that not incrementing B should suffice. $\endgroup$ – Ashok Bijoy Debnath Nov 20 '15 at 16:46
3
$\begingroup$

Project Euler problems (at least the ones that I have done) tend to deal with a lot of number theory topics. So, reading an introductory number theory book could be helpful.

With regards to your particular situation, I suggest finding primes first, then testing the primes for divisibility. That is, to find prime factors of $25$, don't test $1, 2, 3, 4, 5, 6, \ldots$--this would take forever, and you'd also be left with composite factors as well. Rather, find the primes under $25$, and test those: $2, 3, 5, 7,\ldots$ This will be much faster.

Also, you may want to research prime-finding algorithms. If you start dealing with elliptic curves, that's probably overkill for Project Euler--there are some simple, yet effective, algorithms out there.

$\endgroup$
  • $\begingroup$ Wouldnt the action of finding all the primes be just as computationally extensive? Would you have a book reccomendation in mind? $\endgroup$ – Senjai May 12 '13 at 18:06
  • $\begingroup$ @Senjai As for books... I don't know. I picked up my knowledge from Wikipedia and Wolfram Alpha. As for the computationally extensive nature of finding primes: The Big-O asymptotic nature of a prime sieve is the same as that of factoring the way you are. However, Big-O is not the only thing that matters--a prime sieve takes into account the primes its already found, only has to go to the $\sqrt{n}$ to find all primes under $n$, and uses addition operations instead of division. (Small benefit, but its still there.) I'd suggest looking at the Sieve of Eratosthenes‎. $\endgroup$ – apnorton May 12 '13 at 19:22
  • $\begingroup$ I'll check it out. How do you READ Wikipedia, I cant really understand all of the equations and algorithms on there. $\endgroup$ – Senjai May 12 '13 at 20:31
  • $\begingroup$ @Senjai It takes a while. :) I just kept googling when I didn't understand something. $\endgroup$ – apnorton May 12 '13 at 20:41
  • $\begingroup$ Thanks anorton :) I'll upvote you when I get the rep to do so $\endgroup$ – Senjai May 12 '13 at 21:17
1
$\begingroup$

The number looks small enough to be brute-forced on a computer. Just try every possible factor, starting with 2, 3, 4, ... and keep dividing them out as long as the division comes out even. Then continue looking for factors of the quotient. You don't even need to explicitly restrict to primes, because any composite number you try simply won't divide the quotient so far (why?).

If you reach a trial factor that's less than the square root of the number you're dividing into, you know that the larger number must be the last prime factor. So there cannot possibly be more than a few million trial divisions to do.

$\endgroup$

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