Python Program to Print Prime Factor of Given Number

What Are Prime Factors?

Prime factors of a number are the prime numbers that divide the number exactly without leaving any remainder. For instance,

• The prime factors of 12 are 2, 2, and 3, because 12=2×2×3.
• The prime factors of 28 are 2, 2, and 7, because 28=2×2×7.

Steps to Find Prime Factors

To determine the prime factors of a number, do the following:

1. Start dividing that number by 2 until no further division is possible.
2. Move to the next smaller prime number (e.g., 3, 5, etc.) and repeat the process.
3. Continue this process until the number becomes 1.

Python Code

Here’s a Python program that calculates the prime factors of a given number:

def prime_factors(n):
    # List to store prime factors
    factors = []

    # Step 1: Divide by 2 until the number becomes odd
    while n % 2 == 0:
        factors.append(2)
        n //= 2

    # Step 2: Check for odd factors from 3 onwards
    # We only check up to √n for efficiency
    i = 3
    while i * i <= n:
        while n % i == 0:
            factors.append(i)
            n //= i
        i += 2  # Move to the next odd number

    # Step 3: If n is still greater than 2, it is a prime number
    if n > 2:
        factors.append(n)

    return factors

# Input from the user
number = int(input("Enter a number to find its prime factors: "))

# Call the function and print the result
if number > 1:
    print(f"The prime factors of {number} are: {prime_factors(number)}")
else:
    print("Enter a number greater than 1.")

Detailed Explanation of Code

1. Function Definition

def prime_factors(n):

This defines a function named prime_factors that takes an integer n as input.

2. Initialize an Empty List

factors = []

We create a list called factors to store the prime factors of the number.

3. Divide by 2 (Smallest Prime Number)

while n % 2 == 0:
    factors.append(2)
    n //= 2

• while n % 2 == 0: n is divisible by 2. Then, 2 is a factor.
• factors.append(2): Add 2 to the list of factors.
• n //= 2: Divide n by 2 (integer division) and continue checking.

This step deals with all factors of 2 and leaves the remaining n odd.

4. Check Odd Numbers Starting from 3

i = 3
while i * i <= n:
    while n % i == 0:
        factors.append(i)
        n //= i
    i += 2

• Start with i = 3 (the next prime number after 2).
• while i * i <= n: We only check up to the square root of n for efficiency.
• If n % i == 0, i is a factor. Add i to factors list and divide n by i.
• Increment i by 2 to skip even numbers (which cannot be prime, except 2).

5. Handle Remaining Prime Number

if n > 2:
    factors.append(n)

If n is greater than 2 after all the above steps, it means n itself is a prime number. Add it to the list.

6. Input and Output

number = int(input("Enter a number to find its prime factors: "))

This takes an integer input from the user.

if number > 1:
    print(f"The prime factors of {number} are: {prime_factors(number)}")
else:
    print("Enter a number greater than 1.")

If the input is greater than 1, call the prime_factors function and print the result. Otherwise, print an error message.

Example Output

Input:

Enter a number to find its prime factors: 28

Output:

The prime factors of 28 are: [2, 2, 7]

Key Points to Remember

1. A prime number has only two divisors, namely 1 and itself.
2. Efficiently finding prime factors involves dividing the number repeatedly, starting from the smallest prime (2) and moving upwards.
3. Checking divisors up to the square root reduces the computation time.