Python Program to find Prime factors of given integer

In this tutorial, you will learn to write a Python program to find the Prime factors of a given input integer. Prime factorization is a mathematical process of breaking down a number into its prime factors.

We can also say that it is a representation of a composite number as a product of its prime factors. In this post, we will see the various logic to write a Python program to find prime factors of a given integer.

To find the prime factors of a given integer we have to factorize it. Factorization means finding the prime numbers that divide the given integer. We can use different methods to factorize the integer. One of the methods is trial division. is trial division this method, we divide the number by the smallest prime factor, then divide the quotient by the next smallest prime factor, and continue the process until we reach a quotient of 1.

Using Trial Division

In this method, we will use trial division to find the prime factors of a given integer. We will start with the smallest prime factor and divide the integer until the quotient becomes 1. If the quotient is divisible by a prime factor, we will add that factor to the list of prime factors.

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

num = int(input("Please enter a number: "))
print("Prime factors of", num, "are:", prime_factors(num))

Output :

Enter a number: 24
Prime factors of 24 are: [2, 2, 2, 3]