Python Algorithms – Factorizing Numbers in the Billions

algorithmsmathpython

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

Best Answer

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;
}
Related Topic