Find Prime Factors of an Integer Number in Python

In this tutorial, we will learn to write a Python program to find all prime factors of an Integer number. We have a challenge to write a Python program that takes integer input from the user and returns the list of prime factors of that number.

For Example:
120 = [2, 2, 2, 3, 5]
17 = [17]
15 = [3, 5]

What are prime factors?

A prime factor is a prime number that divides another number exactly, without having any remainder. In other words, we can say that if a prime number P divides a positive number N (where N != 1, N not equal to 1), then P is a prime factor of N. The prime factors of a number are the prime numbers that multiply together to give the original number.

For example, let’s consider a number 630. The prime factorization of 630 is the expression of 630 as a product of prime numbers.

630 = 2 x 3 x 3 x 5 x 7

Here, 2, 3, 5, and 7 are the prime factors of 630. 2, 3, 5, 7 are the prime numbers and when we multiply these numbers together (2 x 3 x 3 x 5 x 7), they result in the original number 630.

Prime factorization is a fundamental concept in number theory and is useful in various mathematical applications.

How are we going to find the result?

For example, let’s consider the input number 120. We will follow the below steps to find the list of prime factors of 120:

1. We will start dividing the given number sequentially large values, starting from 2 to see which one divides the Integer number exactly without having any remainder.
2. If the number is divided by 2 exactly without leaving any remainder then we will divide the number and will store number 2 in the list.
3. If the number is not divided by 2 exactly then we will increase the divisor number sequentially and divide the input number. If an increased divisor number can divide the input number exactly without leaving any remainder then we will again append the divisor number into the list.

From the above steps for the number 120, we will get divisor 2 first, then again we will divide the quotient of 120 / 2 = 60. The same is repeated until we get the last divisor of the quotient.

For example, let’s consider dividing 120 and storing the result in the list:

• 120 / 2 = 60
• 60 / 2 = 30
• 30 / 2 = 15
• 15 / 2 = 7.5 Here, a remainder is remaining. So, we will increase the divisor by one.
• 15 / 3 = 5
• 5 / 5 = 1

The final result will be [2, 2, 2, 3, 5].

Program 1: Find prime factors of an Integer number

def get_prime_factor(n: int):
    """
    Get prime factors of a number.
    For example: 120 = [2, 2, 2, 3, 5]
    17 = [17]
    @param n: n is an Integer number
    return list
    """
    divisor = 2
    factor_list = []
        
    while n >= divisor:
        # if number n is divided exactly, without leaving any remainder then append the divisor into the list
        if n % divisor == 0:
            factor_list.append(divisor)
            n = n // divisor
        else:
            # increase divisor sequentially
            divisor += 1
    
    # return the list
    return factor_list

N = int(input("Please enter an Integer number: "))
result = get_prime_factor(N)
print(result)

Output

Please enter an Integer number: 120
[2, 2, 2, 3, 5]

Explanation:

• In the above program, we are taking input from the user by using the input function and converting that number to integer form because we need an integer input to find prime factors.
• Calling the function get_prime_factor() with parameter N.
• Inside the function, create two variables: divisor as integer and factor_list as List type.
• Iterating numbers n through while loop till n >= divisor.
• If the number n is exactly divided by the divisor without leaving any remainder then append the divisor in the factor_list and change the value of n which means assigning the quotient to n and iterating the loop again with a valid condition.
• If the number n is not exactly divided by the divisor then increase the divisor sequentially and execute the next iteration.
• At the end, return the factor_list output and print the result on the display screen.

Program 2: Find prime factors of an Integer number in an optimized way

The above program is also optimized but you can see that the divisor is increasing sequentially and sometimes, a sequential number is not needed to divide the Integer number. For example, if a number is divided by 2 already then it can’t be divided by 4 because it could be divided by 2 X 2. Also, Even numbers are not prime numbers except 2.

So, we can increase the divisor number by 2 instead of 1 to skip the even number as the divisor. We will consider only odd numbers as divisors except 2. The below-given program to find prime factors of an integer number in Python.

from math import isqrt

def get_prime_factors(n):
    """
    Get prime factors of a number.
    For example: 120 = [2, 2, 2, 3, 5]
    17 = [17]
    @param n: n is an Integer number
    return list
    """
    factor_list = []
    # Handle divisibility by 2 separately
    while n % 2 == 0:
        factor_list.append(2)
        n = n // 2

    # Check odd divisors starting from 3
    divisor = 3
    limit = isqrt(n) + 1
    while n > 1 and divisor <= limit:
        if n % divisor == 0:
            factor_list.append(divisor)
            n = n // divisor
        else:
            divisor += 2  # Skip even numbers

    if n > 1:
        factor_list.append(n)

    return factor_list

N = int(input("Please enter an Integer number: "))
result = get_prime_factors(N)
print(result)

Output

Please enter an Integer number: 120
[2, 2, 2, 3, 5]

Explanation:

• In the second program, we are taking input from the user by using the input function and converting that number to integer form because we need an integer input to find prime factors.
• Calling the function get_prime_factors() with parameter N.
• Inside the function, defining a variable factor_list as List type to contain the output result which means to contain the prime factors of an integer number.
• Iterating a while loop and checking that the number n is exactly divisor by 2 without leaving any remainder. If Yes, then appending the number 2 into the factor_list and storing the quotient to n to repeat the loop.
• If the first while loop condition does not work, then create a variable divisor and assign a value 3. Another variable limit that contains the square root of n + 1. Here, we are taking a limit to minimize the iteration of the loop.
• If the number n is exactly divided by the divisor without leaving any remainder then append the divisor in the factor_list and change the value n which means assigning the quotient to n and iterating the loop again with a valid condition.
• If the number n is not exactly divided by the divisor then increase the divisor sequentially and execute the next iteration.
• In the next step, if the number n is greater than 1 then append the number n to the factor_list.

You may also like:

• Python Program to Print All Prime Numbers in an Interval
• Python Program to Check Prime Number
• Python Program to Add Three Numbers
• Python Program to Add Two Numbers