Python: Find Prime Factors

1. Introduction

Prime factors of a number are the prime numbers that divide the number exactly, without leaving a remainder. The process of determining these factors is called integer factorization. In this blog post, we will create a Python program that finds all the prime factors of a given number.

2. Program Overview

1. Define a function to check if a number is prime.

2. Define a function to find prime factors of a number.

3. Input a number from the user.

4. Display its prime factors.

3. Code Program

# Python program to find all prime factors of a number

# Function to check if a number is prime
def is_prime(n):
    """Check if a number is prime."""
    if n <= 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

# Function to find prime factors of a number
def prime_factors(n):
    """Find all prime factors of a number."""
    factors = []
    # Check for 2 as a prime factor
    while n % 2 == 0:
        factors.append(2)
        n = n // 2

    # Check for prime factors from 3 onwards
    for i in range(3, int(n**0.5)+1, 2):
        while n % i == 0:
            factors.append(i)
            n = n // i

    # If the remaining number is a prime greater than 2
    if n > 2 and is_prime(n):
        factors.append(n)

    return factors

# Input the number
num = int(input("Enter a number: "))

# Display its prime factors
print(f"Prime factors of {num} are: {prime_factors(num)}")

Output:

Enter a number: 315
Prime factors of 315 are: [3, 3, 5, 7]

4. Step By Step Explanation

1. We begin with defining the is_prime function to check if a given number is prime. This function uses a basic optimization to only loop until the square root of n and check for divisibility.

2. Next, we define the prime_factors function which first checks for 2 as a prime factor and then for prime factors starting from 3 onwards.

3. The outer loop in the prime_factors function runs until the square root of n. For each potential factor, the inner while loop checks divisibility and reduces the number n.

4. In the main body of the program, we collect the number from the user and then display its prime factors.