d20 + 1

Programming, Table Top Games, and Food Snobbery

Tools for Project Euler: Prime Factorization

I started doing Project Euler a few weeks ago, and have noticed several techniques that have come up time and again to help solve the problems.  So, rather than post solutions (which you can actually find mine on my github, linked in an earlier post) I decided I’d post some helpful functions.

The function I’m going to go over in this post, is an easy way to find the prime factorization of a number, something that is generally not an easy feat.

Basically, there are two things you want to check when you do this:

  1. Make sure that you number is prime
  2. Make sure that it goes into whatever you’re factoring

Whenever I think of prime factorization, I think of that tree they made us draw out whenever they first introduced the concept (I honestly don’t remember if it was elementary or middle school).  You start at the top and work down to find the prime factors.  As it turns out, that is no where near the best way to do it.

In fact, if you start at the bottom, and work up, you can cut out the primality test from you two checks.  By starting at two and working up, you guarantee that the first number you find that is a factor of your number is prime.  There are no smaller integers that can go into it, because otherwise you would have found them first to go into your big number.  So, we start with 2 (the smallest prime), find out if it goes into your number.  If it does, we divide the big number by two, and continue with the now smaller number, if it doesn’t we increment.  So:

def prime_factors(big_num):
    num = big_num
    x = 2
    list_primes = []
    list_exponents = []
    while x < big_num
        if num % x == 0
            num = num / x
            if x in list_primes
                list_exponents[len(list_exponents) - 1] ++
            else
                list_primes.append(x)
                list_exponents.append(1)
        else
            x ++
    factorization = [list_primes, list_exponents]
    return factorization

This seems ok, but still has lots of room for improvement.  First, we’ll work with our while loop’s condition.  While it won’t be wrong to go all the way to the number, you are looking at a lot more numbers than you need to be.  An obvious boundary is big_num/2.  That effectively halves the numbers you need to look at.  Better yet, we can stop at the square root of big_num, and if num is greater than 1 at the end of the look, add it to the list of factors.  Something else to be aware of:  every time you iterate through a while loop, the condition on top must be recalculated.  This means, that you can speed up your run time considerably by storing the square root in a variable, and then setting that as the limit, rather than calculating the square root every iteration.  So now, we end up with:

def prime_factors(big_num):
    num = big_num
    x = 2
    root = big_num ** 0.5
    list_primes = []
    list_exponents = []
    while x < root:
        if num % x == 0:
            num = num / x
            if x in list_primes:
                list_exponents[len(list_exponents) - 1] ++
            else:
                list_primes.append(x)
                list_exponents.append(1)
        else:
            x ++
    if x != 1:
        list_prime.append(x)
        list_exponents.append(1)
    factorization = [list_primes, list_exponents]
    return factorization

Ok, we’re almost done, and the above code will probably be good enough for most problems, but there is one more speed up that I know about.  Once again, we’re going to try and cut down the number of times we need to iterate.  After you get past 2, there are no more even numbers that are prime, so we shouldn’t even bother checking them.  So, what we need to do is find out how many times 2 goes into the number, then, run the loop starting at three and iterating with x += 2.  So our final code snippet for this function is:

def prime_factors(big_num):
    num = big_num
    x = 2
    root = big_num ** 0.5
    list_primes = []
    list_exponents = []
    while x == 2:
        if num % x == 0:
            num = num / x
            if x in list_primes:
                list_exponents[len(list_exponents) - 1] ++
            else:
                list_primes.append(x)
                list_exponents.append(1)
        else:
            x ++
    while x < root:
        if num % x == 0:
            num = num / x
            if x in list_primes:
                list_exponents[len(list_exponents) - 1] ++
            else:
                list_primes.append(x)
                list_exponents.append(1)
        else:
            x += 2
    if x != 1:
        list_prime.append(x)
        list_exponents.append(1)
    factorization = [list_primes, list_exponents]
    return factorization

This function returns a list of lists, the first one has all of the prime factors of a number, and the second one has how many times those factors appeared.  There are probably better ways to do this, but this is how I do it, and so far it’s always been fast enough to for my function to beat the 1 minute mark.

  1. overcyn reblogged this from d20plus1
  2. d20plus1 posted this