Python Program to Find Prime Factors of a Number

If a number p is fully divisible by another number q, then q is said to be a factor of p. Here q will be greater than 1 and less than or equal to p.

So, if a number p is fully divisible by another number q and q is a prime number then q is said to be a prime factor of p.

Prime numbers are those numbers that are only divisible by 1 and themselves. In this article, we will see the code to find the prime factors of a number.

For example:

If we take 5, then prime factors will be:

5 = 5

5 is the only prime factor of 5.

If we take 20, then prime factors will be:

20 = 2 * 2 * 5

If we take 210, then prime factors will be:

210 = 2 * 3 * 5 * 7

Now let’s see the code of this problem. In this code, we will be creating two functions. The first function will help us to know if a number is prime or not. And the second function will help us to print the prime factor of a number.

def isPrime(n):
    """
    Function to return if a number is prime or not
    Input : A Number
    Output : Boolean Value True or False
    """

    # If the Number is less than 2, then returns False
    if n < 2:
        return False
    
    # loop from 2 to n-1, if between this range n is divided by any number 
    # then return False 
    # else return true in the end.
    for i in range(2, n):
        if (n % i == 0):
            return False

    return True

# Function to print the prime factors of a number.
def primeFactor(n):
    """
    Function to print the prime factors of a number.
    Input : Number
    Output : None. It will print the prime factors from the function only.

    """
    if (n < 2):
        print("No Prime Factors")
        return

    i = 2
    # Loop while i is not equal to n
    while (i < n+1):
        # if n is divisible by i and i is a prime number then we have to 
        # print the vlaue of i and update the value of n by dividing it by i.
        # else we just have to increment the value of i by 1.
        if (n % i == 0 and isPrime(i)):
            print(i) # print the value of i
            n = n / i # update the value of n
        else:
            i += 1 # Increase the value of i by 1

# Take the number as input from user in the string format
number = input("Enter the Number : ")

# Convert the string datatype into integer datatype
number = int(number)

# Call the function to print the prime factors of the inputted number
print("Prime Factor : ")
primeFactor(number)

Testcase 1: When the input is 100.

Output:

PS C : \ Users \ ASUS \ Desktop \ Crazy Programmer Work > python -u " c : \ Users \ ASUS \ Desktop \ Crazy Programmer Work \ test.py "
Enter the Number : 100
Prime Factor : 
2
2
5
5

Testcase 2: When the Input is 270270.

Output:

PS C : \ Users \ ASUS \ Desktop \ Crazy Programmer Work > python -u " c : \ Users \ ASUS \ Desktop \ Crazy Programmer Work \ test.py "
Enter the Number : 270270
Prime Factor : 
2
3
3
3
5
7
11
13

We have used two functions to create the whole program.

The first function will tell us if a number is prime or not. It takes an integer and returns a Boolean value (True or false).

The second function will help to print the prime factors of a number. It will take an integer as input and print all the prime factors of that input. It returns None because all the printing is done within the function only.