• Skip to primary navigation
  • Skip to main content
  • Skip to primary sidebar
PythonForBeginners.com

PythonForBeginners.com

Learn By Example

  • Home
  • Learn Python
    • Python Tutorial
  • Categories
    • Basics
    • Lists
    • Dictionary
    • Code Snippets
    • Comments
    • Modules
    • API
    • Beautiful Soup
    • Cheatsheet
    • Games
    • Loops
  • Python Courses
    • Python 3 For Beginners
You are here: Home / Basics / Find Prime Factors Of A Number in Python

Find Prime Factors Of A Number in Python

Author: Aditya Raj
Last Updated: December 22, 2021

You might have heard about factors of a number. Factors of any given number are those numbers that divide the given number completely leaving no remainder. In this article, we will discuss an algorithm to find prime factors of a number in python.

What Are Prime Factors Of A Number?

Prime numbers are those numbers that have only two factors, 1 and the number itself. Also, we can represent any given number as a product of prime numbers. Here, all those prime numbers that we can use to represent any given number are called the prime factors of the given number.

For instance, we can represent 20 as the product of prime number 2 and 5 as 2x2x5. Hence, 2 and 5 are prime factors of 20. Similarly, we can represent any number using a combination of prime numbers.

Algorithm To Find Prime Factors Of A Number

To find the prime factors of a number, we just have to divide the given number using prime numbers. But, how do we know if a factor of the given number is prime or not? To eliminate this problem, we will use repetitive division. Let us take the number 1260 as our running example so that we can find its prime factors.

First, we will divide the given number repetitively by 2 and store the resultant number until the remainder becomes 1. By this, we will make sure that any even number will not divide the resultant. Now, we can skip all the even numbers while finding the factors of the given number. For instance, we will divide 1260 by 2, two times, giving 315 as resultant. Here, you can see that the resultant 315 is an odd number. Hence no even number can be its factor. 

After division by 2, we will repetitively divide the resultant by 3 and store the result until the number becomes indivisible by 3.  By this, we will make sure that any multiple of 3 will not divide the resultant. Here, we will divide 315 by 3, two times, giving 35 as resultant. You can see that no multiple of 3 can divide 35. 

Similarly, we will perform repetitive division using 5,7,9, 11, and other odd numbers until the resultant becomes 1. In this way, we can find the prime factors of any given number. Here, 1260 has 2, 3, 5, and 7 as its prime factors.

Python Program To Find Prime Factors Of A Number

Now, we will implement the algorithm discussed above to find the prime factors of any given number. Here, we will create a set to store the prime factors and implement the above algorithm as follows.

def calculate_prime_factors(N):
    prime_factors = set()
    if N % 2 == 0:
        prime_factors.add(2)
    while N % 2 == 0:
        N = N // 2
        if N == 1:
            return prime_factors
    for factor in range(3, N + 1, 2):
        if N % factor == 0:
            prime_factors.add(factor)
            while N % factor == 0:
                N = N // factor
                if N == 1:
                    return prime_factors


input_number = 20
output = calculate_prime_factors(input_number)
print("Prime factors of {} are {}".format(input_number, output))
input_number = 1260
output = calculate_prime_factors(input_number)
print("Prime factors of {} are {}".format(input_number, output))

Output:

Prime factors of 20 are {2, 5}
Prime factors of 1260 are {2, 3, 5, 7}

Conclusion

In this article, we have discussed and implemented an algorithm to find the prime factors of a given number in python. To learn more about numbers in python, you can read this article on decimal numbers in python. You might also like this article on complex numbers in python.

Related

Recommended Python Training

Course: Python 3 For Beginners

Over 15 hours of video content with guided instruction for beginners. Learn how to create real world applications and master the basics.

Enroll Now

Filed Under: Basics Author: Aditya Raj

More Python Topics

API Argv Basics Beautiful Soup bitly Cheatsheet Code Code Snippets Command Line Comments Concatenation crawler Data Structures Data Types deque Development Dictionary Dictionary Data Structure In Python Error Handling Exceptions Filehandling Files Functions Games GUI Json Lists Loops Mechanzie Modules Modules In Python Mysql OS pip Python Python On The Web Python Strings Queue Requests Scraping Scripts Split Strings System & OS urllib2

Primary Sidebar

Menu

  • Basics
  • Cheatsheet
  • Code Snippets
  • Development
  • Dictionary
  • Error Handling
  • Lists
  • Loops
  • Modules
  • Scripts
  • Strings
  • System & OS
  • Web

Get Our Free Guide To Learning Python

Most Popular Content

  • Reading and Writing Files in Python
  • Python Dictionary – How To Create Dictionaries In Python
  • How to use Split in Python
  • Python String Concatenation and Formatting
  • List Comprehensions in Python
  • How to Use sys.argv in Python?
  • How to use comments in Python
  • Try and Except in Python

Recent Posts

  • Pandas Append Row to DataFrame
  • Convert String to DataFrame in Python
  • Pandas DataFrame to List in Python
  • Solved: Dataframe Constructor Not Properly Called Error in Pandas
  • Overwrite a File in Python

Copyright © 2012–2023 · PythonForBeginners.com

  • Home
  • Contact Us
  • Privacy Policy
  • Write For Us