Subscribe to Dogstopper's Code Mania        RSS Feed

Prime Factorization (Python)

Icon 1 Comments
Python is the language in which I write the majority of my algorithms, which I then port to whatever other other languages I need to. Today I was given the challenge to find all the prime factors of any given number. At first, I thought it was rather difficult, but after a little bit of thinking, I managed to solve this task.

Though it may not have been the best way, it certainly did it. The idea behind my algorithm is for each number, make 2 more entries - the highest factor of that number and the multiplier for it. Then, remove the original number. I had it so that the highest factor (the only potentially non-prime number) was always the first element in the list. Here is an illustration:

# Start
number = 64
factors = []

# Here is what happens to the array
[32, 2] # Highest prime of 64 and related number
[16, 2, 2] # Still keeping highest prime first
[ 8, 2, 2, 2] #...
[ 4, 2, 2, 2, 2] 
[ 2, 2, 2, 2, 2, 2]

So, by always picking the HIGHEST factor, the other number will always be prime. Then it's simply a matter of list management. I have 2 helper functions for this, isPrime() and getMaxFactor(). Let's take a look:
def isPrime(number):
    # 2 is a prime number
    if number == 2:
        return True

    # Make any negative numbers positive!
    if number < 0:
        number *= -1

    # All numbers divisible by 2 are non-prime
    if number % 2 == 0:
       return False

    # See if num/3, num/5, num/7 ... are prime checking
    count = int(math.sqrt(number))
    for x in range (3, count+1, 2):
        if number % x == 0:
            return False
        return True

def getMaxFactor(number):
    # Max possible number is number/2
    count = number/2

    # Subtract until we reach a factor, every number
    # is divisible by AT LEAST 1
    while count > 0:
        if number % count == 0:
            return count
        count -= 1

Now, the modulo operator (%) in case you don't know, returns the remainder after dividing. If the remainder is ever zero, then the number evenly divided into another number (meaning it is non-prime, but is a factor).

These are just the helper functions though; the real meat is in the PrimeFactorization() function:
def PrimeFactorization(number):
    # Start with first 2 numbers
    l = [getMaxFactor(number)]

    # Progressively evaluate the first index until
    # it is prime. 
    while True:
        if not isPrime(l[0]):
            high = getMaxFactor(l[0])
            low = l[0]/high
            del l[0]

            l = [low] + l
            l = [high] + l
    return l

You see the pattern now, how the first index will always be the potentially non-prime number. That what we add low to the beginning of the array before the high number - so that it will appear at the start.

So there you have it! Prime Factors! Have fun!

1 Comments On This Entry

Page 1 of 1


10 May 2010 - 10:53 PM
I like how you shortened the amount of "n" traversed in the for loop by half just by checking one mod function before it.

It makes me wish that there could be a dynamic function that modifies the for loop to traverse larger spans based on the what numbers are already found to not work in the for loop! (kind of like what the Sieve of Eratosthenes does, except updated for the range jumped between numbers not tested)

Anyways.. :offtopic:

Good program.
Page 1 of 1

February 2021

2122232425 26 27

Recent Entries

Search My Blog

Recent Comments

0 user(s) viewing

0 Guests
0 member(s)
0 anonymous member(s)