Largest prime factor of 600851475143 [duplicate]

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.

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.

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.

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.