Python Program to Find Prime Factors of a Number

 In this post I am going to write a program in python that finds all the prime factors of a number. I am going to start by writing an empty function and a test.

  def get_prime_factors(number):
      prime_factors = []
      return prime_factors
      
  if __name__ == "__main__":
      n = 8
      expected = [2, 2, 2] 
      result = get_prime_factors(n)
      assert expected == result, result
Now, if you run the program above, it will give an AssertionError, as we are returning an empty list. Let's write some code to make our test pass. 
    def get_prime_factors(number):
        prime_factors = []
        
        while number % 2 == 0:
            prime_factors.append(2)
            number = number // 2
            
        return prime_factors
The program will work for multiple of 2's. Our next task is to find the other prime factors. For example, prime factors of 10 are 2 and 5. We shall add this test case first and then write code to pass this test. If you have studied prime numbers before, then you might remember that if the number itself is not prime, then you will find all the prime factors in the range from 2 to square root of n. So we shall use a loop to try every number upto square root of n to check if that number is a factor of n. And as we already tried to divide the number by 2, we can try only odd numbers. 
    from math import sqrt
    
    def get_prime_factors(number):
        prime_factors = []
        
        while number % 2 == 0:
            prime_factors.append(2)
            number = number // 2
            
        sq_root = int(sqrt(number))
        for m in range(3, sq_root+1, 2):
            if number % m == 0:
                prime_factors.append(m)
                number = number // m
                
        return prime_factors
We made some good progress. However, the get_prime_factors function above won't pass the test case for 10. Because in the first while loop, number is divisible by 2, so we shall add 2 to the list of prime factors. Then we divide the number by 2, so it becomes 5 (10 // 2). And the value of sq_root is 2, so the value of m in the for loop will be 3 (for m in range(3, 3, 2)). So we didn't get anything out of that loop. Because here 5 itself is a prime number. So after the for loop, we need to check if number is still greater than 1. And if it is, then we can safely assume that it's a prime number (and a prime factor of number), thus add to our list of prime factors. If you spend some time, you will be able to complete the code by yourself. And don't forget to test the code with different values of n (1, 2, 4, 5, 25, 100, 101). I hope you found it useful.

You can find the full code here.

Comments

Post a Comment

Popular posts from this blog

Strip HTML tags using Python

We often need to strip HTML tags from string (or HTML source). I usually do it using a simple regular expression in Python. Here is my function to strip HTML tags: def remove_html_tags(data): p = re.compile(r'<.*?>') return p.sub('', data) Here is another function to remove more than one consecutive white spaces: def remove_extra_spaces(data): p = re.compile(r'\s+') return p.sub(' ', data) Note that re module needs to be imported in order to use regular expression. Here you can find an updated code that gets the text from html: http://love-python.blogspot.com/2011/04/html-to-text-in-python.html
Read more

lambda magic to find prime numbers

Find prime number up to 100 with just 3 lines of code. The 4th line is for printing ;) nums = range(2, 100) for i in range(2, 10):     nums = filter(lambda x: x == i or x % i, nums) print nums Isn't it amazing? Check my new post about Prime number: http://love-python.blogspot.com/2010/11/prime-number-generator-in-python-using.html
Read more

Convert text to ASCII and ASCII to text - Python code

Python has a very simple way to convert text to ASCII and ASCII to text. To find the ASCII value of a character use the ord() function. Example: >>> ord('B') 66 To get a character from it's ASCII value use the chr() function. Example: >>> chr(65) 'A' Here is a program to get the list of all characters along with their values: # program to print the list of characters and their ASCII values for value in range(0, 255): print "ASCII Value:", value, "\t", "Character:", chr(value), "\n" Here is another simple ASCII encoding-decoding program: # Convertion from text to ASCII codes message = raw_input("Enter message to encode: ") print "Decoded string (in ASCII):" for ch in message: print ord(ch), print "\n\n" # Convertion from ASCII codes to text message = raw_input("Enter ASCII codes: ") decodedMessage = "" for item in message.split(): decodedMessage += chr...
Read more