This example uses an algorithm to find a number's prime factors. For other interesting algorithms, see my book Essential Algorithms, Second Edition. The book describes many fascinating algorithms in pseudocode with source code available for download in Python and C#.

Title: Find a number's prime factors in Python

Once upon a time, I read an article where the author said something like this:

My professor asked us whether we had prime factored our Social Security numbers yet. Being a normal person, I laughed with everyone else. Being a nerd, I managed to resist for only three days.

Of course I immediately rushed to my computer and wrote a prime factoring program. At the time it was kind of hard because the computer I was using didn't have integers big enough to hold Social Security numbers. This is a lot easier now, particularly in Python which can handle arbitrarily large integers.

This example uses the following find_factors method to find a number's prime factors.

def find_factors(num): '''Return the number's prime factors.''' result = [] # Take out the 2s. while num % 2 == 0: result.append(2) num //= 2 # Take out other primes. factor = 3 while factor * factor <= num: if num % factor == 0: # This is a factor. result.append(factor) num //= factor else: # Go to the next odd number. factor += 2 # If num is not 1, then whatever is left is prime. if num > 1: result.append(num) return result

Next, for odd numbered values of factor = 3, 5, 7, and so on, the program determines whether factor divides evenly into num. If factor does divide evenly into num, the program adds factor to the list of factors and divides num by it. If factor does not divide num evenly, the program adds 2 to factor to check the next odd number.

The program stops when factor * factor is greater than num.

The following code shows how the program uses this method.

import random for i in range(10): num = random.randrange(100, 1000000) print(num) print(find_factors(num))

Download the example to see all of the details.

Finding Primes in Your Head

In fact, there are some easy tricks that you can use to tell if a number is divisible by 2, 3, 5, or 7.

• 2: If the number's last digit is 0, 2, 4, 6, or 8, then the number is divisible by 2.
• 3: If the sum of the number's digits is divisible by 3, then so is the number. If the sum of the digits is too big to make it obvious, add its digits and try again. For example, consider 1,057,548,393. Adding its digits gives you 1 + 0 + 5 + 7 + 5 + 4 + 8 + 3 + 9 + 3 = 45. It's easy to know that 45 is divisible by 3, but if you don't know that you can add its digits to get 4 + 5 = 9, which is definitely divisible by 3. That means the original number 1,057,548,393 is also divisible by 3. In fact, you can use the find_factors function to learn that this 1,057,548,393 = 3 * 3 * 3 * 3 * 3 * 11 * 17 * 17 * 37 * 37.
• 5: If the number's last digit is 0 or 5, then the number is divisible by 5.
• 7: This one is trickier. Remove the number's last digit, double that digit, and subtract from the rest of the number. If the result is 0 or divisible by 7, then the original number is divisible by 7. For example, consider the number 10,647:
  • 10647: 1064 - 2 * 7 = 1064 - 14 = 1050
  • 1050: 105 - 2 * 0 = 105
  • 105: 10 - 2 * 5 = 10 - 10 = 0. This is 0 so 10,647 is divisible by 7. (The find_factors function says 10,647 = 3 * 3 * 7 * 13 * 13.)