• Skip to primary navigation
  • Skip to main content
  • Skip to primary sidebar

The Programming Expert

Solving All of Your Programming Headaches

  • HTML
  • JavaScript
  • jQuery
  • PHP
  • Python
  • SAS
  • Ruby
  • About
You are here: Home / Python / Python Prime Factorization – Find Prime Factors of Number

Python Prime Factorization – Find Prime Factors of Number

February 7, 2022 Leave a Comment

Prime factorization is easy to do in Python. We can find the prime factors of a number by defining a function, applying some logic to get the prime factors, and returning a list of the prime factors.

Below is a function which will get the prime factorization of a number in Python.

def prime_factorization(n):
    prime_factors = []
    while (n % 2 == 0):
        n = n / 2
        prime_factors.append(2)
    for i in range(3, int(n**0.5 + 1), 2):
        while (n % i == 0):
            n = n / i
            prime_factors.append(i)
    if n > 2:
        prime_factors.append(int(n))
    return prime_factors

Prime factorization is a way of expressing a number as a product of its prime factors. A prime factor is a prime number, and prime factorization is the process to get all of the numbers which when multiplied equals the given number.

In Python, we can write our own function to find the prime factors of any positive integer. We will be using the division method to find prime factors.

To get the prime factors of a number, we need to do the following:

First, if the given number is even, then we know 2 is a prime factor and we should divide the given number by 2. Until the number is odd, then we should continue dividing by 2.

Next, the temporary number that we are dividing will be odd, and we need to loop through the odd numbers 3 until the square root of the temporary number to see if there are any numbers which can divide our temporary number.

Why are we doing this?

First, we only need to check odd numbers because we’ve taken out all of the even factors in the first step. Second, we only need to check until the square root of the temporary number because of the statement: Every composite number has at least one prime factor less than or equal to the square root of itself.

Finally, if the temporary number is greater than 2, then we know the temporary number is prime (i.e. not composite) and should be added to our list.

Below is the final function to find the prime factors of a given number using Python.

def prime_factorization(n):
    prime_factors = []
    while (n % 2 == 0):
        n = n / 2
        prime_factors.append(2)
    for i in range(3, int(n**0.5 + 1), 2):
        while (n % i == 0):
            n = n / i
            prime_factors.append(i)
    if n > 2:
        prime_factors.append(int(n))
    return prime_factors

Finding Prime Factorization of Numbers Using Python

We can now use our function for prime factorization above to find the prime factorization of some different numbers.

Let’s find the prime factorization of a handful of numbers in the following example.

def prime_factorization(n):
    prime_factors = []
    while (n % 2 == 0):
        n = n / 2
        prime_factors.append(2)
    for i in range(3, int(n**0.5 + 1), 2):
        while (n % i == 0):
            n = n / i
            prime_factors.append(i)
    if n > 2:
        prime_factors.append(int(n))
    return prime_factors
        
print(prime_factorization(10))
print(prime_factorization(13))
print(prime_factorization(90))
print(prime_factorization(121))
print(prime_factorization(749))
print(prime_factorization(283))

#Output:
[2, 5]
[13]
[2, 3, 3, 5]
[11, 11]
[7, 107]
[283]

Hopefully this article has been useful for you to learn how to do prime factorization of numbers in Python.

Other Articles You'll Also Like:

  • 1.  Check if Word is Palindrome Using Recursion with Python
  • 2.  How to Check if a Dictionary is Empty in Python
  • 3.  Sort Series in pandas with sort_values() Function
  • 4.  Calculating Sum of Squares in Python
  • 5.  Using Python to Convert Decimal to String
  • 6.  Remove All Instances of Value from List in Python
  • 7.  Negate Boolean in Python with not Operator
  • 8.  Comparing Datetimes in Python
  • 9.  pandas str replace – Replace Text in Dataframe with Regex Patterns
  • 10.  Inverting Dictionary Variables in Python with Dictionary Comprehension

About The Programming Expert

The Programming Expert is a compilation of a programmer’s findings in the world of software development, website creation, and automation of processes.

Programming allows us to create amazing applications which make our work more efficient, repeatable and accurate.

At the end of the day, we want to be able to just push a button and let the code do it’s magic.

You can read more about us on our about page.

Reader Interactions

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Primary Sidebar

About The Programming Expert

the programming expert main image

Welcome to The Programming Expert. We are a group of US-based programming professionals who have helped companies build, maintain, and improve everything from simple websites to large-scale projects.

We built The Programming Expert to help you solve your programming problems with useful coding methods and functions in various programming languages.

Search

Learn Coding from Experts on Udemy

Looking to boost your skills and learn how to become a programming expert?

Check out the links below to view Udemy courses for learning to program in the following languages:

Copyright © 2023 · The Programming Expert · About · Privacy Policy

x