# What would be an appropriate algorithm to factorise numbers in the range of a few billion?

I'm learning Python at the moment and to give me reasons to apply what i'm learning I'm having a crack at some of the problems on Project Euler

I'm currently on number 3, which is to determine the highest prime factor of said number.

I've deduced I need to probably have two algorithms, one to determine primality, and the second which would involve finding factors of the number.

So i've been reading up on Wiki articles. Trying to determine what might be the best algorithm to use and how to go about it.

But it's been a while since i've done some hardcore maths based programming and i'm struggling to start somewhere.

I was looking at using Fermat's factorization method with inclusion of Trial by Division but I don't want to make something too complicated I'm not after to crack RSA I just want two algorithsm suitable for my problem and there in lies my question.

What algorithms would you use for testing for primality / factoring a number that are suitable to the problem at hand?

Edit

Thank you all for your answers and insights they have been most helpful I upvoted all that were useful either through advice or through there own Euler experiences. The one I marked as right was simply the most useful as It gave me a proper place to start from which was a push in the right direction. Thanks again =)

-
Such problems may best use parallel processing. – NoChance Dec 22 '11 at 11:03
Maybe you are right in general, but for project euler it is usually more important to find a "smart" algorithm. They are a lot faster than parallelizing brute force approaches. – sebastiangeiger Dec 22 '11 at 11:28
This is a mathematically difficult problem, and you will not find an ideal solution. – DeadMG Dec 22 '11 at 22:45

My approach for those problems is usually this one: build the simplest possible algorithm to solve it, which is usually a brute force naive approach, and then test/figure mathematically whether or not it's too slow. Most of the time it's good enough. When it's not you have a clear starting point to work on and optimize things around until the algorithm is efficient enough.

Here's a simple algorithm to solve Problem 3 on Project Euler (in C, but translating it to the Python should be trivial):

``````#include <stdio.h>
#include <math.h>

int isPrime(int n){
int i;

if (n==2)
return 1;

if (n%2==0)
return 0;
for (i=3;i<sqrt(n);i+=2)
if (n%i==0)
return 0;
return 1;
}

int main(){
long long int n = 600851475143;
int i = 3;

while (i<50000){
if (isPrime(i))
if (n%i==0)
printf("%d\n",i);
i+=2;
}
return 0;
}
``````
-
I'd say using `isPrime` is an overkill. Just doing `n/=2` while `n%2==0` and then starting `i` with 3 and then looping `if (n%i==0) n/=i; else i+=2;` is enough (well, it can be stopped once `i*i > n`). – herby Dec 22 '11 at 14:20
My experience solving project euler is that this approach is working for the earlier problems but you probably have to refine it when solving more complicated ones. – sebastiangeiger Dec 22 '11 at 14:23
@Sebastian, I am on problem 73, and yeah down the road most naive approaches stop working. But hey, why complicate things before you need? – daniels Dec 22 '11 at 17:56
@daniels: I may be being dumb here. How does this solve the problem? a) 50000 seems terribly arbitrary. b) You're printing out all prime factors, not just the highest. c) Checking whether it's prime before checking if it is a factor seems wasteful. d) 2 is a prime number. – pdr Dec 22 '11 at 20:50
@pdr, a) prime factors don't go up that fast, so I figured 50000 would be big enough. If it was not you could always repeat with 100000 or sqrt(n). b) right, which means you just need to look at the last one printed (I printed all just to see what was going on). c) I agree inverting the tests would be more efficient, but makes no difference in this case (i.e., you would gain some milliseconds) d) yep I forgot that special case on my isPrime() function. – daniels Dec 22 '11 at 22:21

It's well worth writing some code that does factorising and prime-finding (basically the same thing) because you will probably re-use in lots of other Euler questions. You will be able to improve the code for later questions and perhaps look into non-exhaustive primality tests if you find its no longer efficient enough, so I suggest the simplest approach for now is to:

• Write a simple loop which finds all the prime numbers (ie. for each number, test its divisibility by each previously found prime, and if they all fail, add it to the list of primes).
• Try to divide the number you're trying to factorise by each prime up to the square root of the number.
-

Actually this is an area of active research in Mathematics and Computer Science. The wikipedia article gives a good overview:

http://en.wikipedia.org/wiki/Integer_factorization

Pick any algorithm you like/find interesting, and have a go at it.

You'll probably have to make a tradeoff: Most of the "good" algorithms require a fair bit of Math background to really understand (though you could implement them without completely understanding them).

If you don't know where to start, I'd recommend the quadratic sieve:

It does not require insane Math knowledge, yet performs well.

-

I solved some ProjectEuler problems some time ago in Ruby using trial division with prime numbers.

I found that generating the prime numbers was far more critical than the actual factorization algorithm. As soon as I replaced my naïve prime number generation approach with a sieve my execution times came down to a reasonable amount.

-

Keeping it very simple ...

Finding the factors of X: I would start (n) at 2 and work up to the integer (floor, not round) of the square-root of X. If dividing X by n yields Y and Y is an integer, both n and Y are factors. The lowest values of n will yield the highest values of Y.

Primality of Y: Again, loop (m) from 2 to the square root of Y and see if Y / m is an integer. If it is then Y is not prime. Go back to find another factor.

If m hits the root of Y, you have your prime number. Stop looking. Y is the answer.

If n hits the root of X, there aren't any prime factors.

-

``````--  Problem is to find the largest prime factor of 600851475143
module Factor (testval, bigfactor) where
testval = 600851475143

bf' :: Integer -> Integer -> Integer

bf' f x | (f == x)         = f
| ((mod x f) == 0) = bf' f (div x f)
| True             = bf' (f+1) x

bigfactor :: Integer -> Integer

bigfactor x | (x <  1) = error "Parameter less than 1"
| (x == 1) = 1
| True     = bf' 2 x
``````

Basically, there's no need to test for primality. If you divide out the factors you find (and make sure you handle repeating factors), then a non-prime factor can never occur, because a non-prime factor is a product of smaller prime factors.

Loaded and ran this with GHCi - it's instant, and I've now got a grand total of 4 (yes, four!) Euler problems solved.

-

I'm also shaping up my Python knowledge and have too started answering Project Euler's problems on my github repo: https://github.com/rentes/Euler.

For Problem 3, I have programmed a simple solution which is based on the following premisses:

1) given a positive integer n, I start to divide it by 2, 3, ..., m, and if I find that m is a prime factor, I add it to a list. I am not adding to the list multiples of already discovered prime factors. For instance, 4 is a multiple of 2, so 4 is not added to this list.

2) I then multiply each prime on the list to see if it equals n. If equal, we have found all prime factors of n. If not, continue dividing n by the next m number, until mutiplying all prime factors equals n or m reaches n.

Please see https://github.com/rentes/Euler/blob/master/problem3.py for more details. I've added comments that will help you understand what I programmed. It is a simple solution, and I am sure it is not the fastest solution, but it works and it is simple enough to understand.

Best regards

-