Online Ethical Hacking Course

Apply Now

Examples

Program to Find Prime Factors of a Number in Python

In number theory and mathematical algorithms, prime factorization is a fundamental concept that helps us understand the building blocks of numbers. Prime factors are the prime numbers that divide a given number evenly, without leaving a remainder. Finding the prime factors of a number in Python allows us to break it down into its prime components, providing insights into its unique factorization.

In this tutorial, we will explore a program to find prime factors in Python. We will provide a step-by-step guide, complete with examples, to help you understand the concept and implement it in your Python programs effectively.

It is important to know the difference between factors and prime factors. Factors of a number are the numbers that divide it evenly, whereas prime factors are the factors that are prime numbers. 

For example, the factors of 12 are 1, 2, 3, 4, 6, and 12, but the prime factors are 2 and 3. 

Python, with its simplicity and versatility, provides an excellent platform for finding the prime factors of a number. By mastering this program, you will enhance your skills in number manipulation, algorithmic thinking, and mathematical analysis.

So let's get started and learn to find prime factors of a number in Python.

Program for Prime Factors of a Number in Python

Here's a Python program to find prime factors of a number:

Code

def find_prime_factors(n):
    factors = []
    divisor = 2

    while divisor <= n:
        if n % divisor == 0:
            factors.append(divisor)
            n = n / divisor
        else:
            divisor += 1

    return factors

# Taking input from the user
number = int(input("Enter a number: "))

print("Prime factors of", number, "are:", find_prime_factors(number))

Output

Enter a number: 140
Prime factors of 140 are: [2, 2, 5, 7]

Explanation

  • The find_prime_factors function takes an input number n for which we want to find the prime factors.

  • We initialize an empty list factors to store the prime factors.

  • We start with the smallest prime number, which is 2, and repeatedly divide the number n by 2 until it is no longer divisible by 2. At each division, we append 2 to the factors list.

  • Then, we move on to the next prime number, which is 3, and repeat the same process until we reach the square root of the number n. If n is divisible by the current prime number, we append it to the factors list and update n by dividing it by the current prime number.

  • Finally, if n is not equal to 1, it means that it is a prime number greater than the square root of the original input. So, we add it to the factors list.

  • The function returns the factors list.

  • We take input from the user using input() and convert it to an integer using int().

  • We call the find_prime_factors function with the input number and print the list of prime factors.

Practice More Python Programs:

Useful Python Resources:

Python Course