Prime Factorization in Python

by

In the previous article we looked at how we can obtain the first digit of any given number, now we will look at how we can achieve prime factorization in Python. We are given a number n, we need to find prime factorization of this number. We need to consider all the divisors of the number, and we need to find out how many times they divide the given number.

For example if we see the number 100, it will have the prime factors:

2, 2, 5, 5

If we multiply all these prime numbers together we get the original number(100). In the case of 13, which is a prime number the result would be 13 itself. For 15 there would be two prime factors: 3 & 5.

Implementation of Prime Factorization in Python

We will run a loop from 2 to 100, and find out the prime factors of the number within that range. We need to check for two conditions for each number, first thing is whether it’s a prime number. The second requirement is that it should be dividing n. For example if the number is 2 we check if it divides the given number and whether 2 is a prime number. If we check for the number 3 and the given number is 100, it does not divide 100 so we discard that number. The number 4 is not a prime number, so we do not consider it. But the number 5 would both divide the given number and is itself a prime number. 6 does not divide, and we proceed with the various numbers until 100

The algorithm for checking these conditions should follow this kind of logic:

x=i
while n % x==0:
     print(i)
     x=x*i

Let us see how we can implement this algorithmic logic in the form of functions in the program.

def isPrime(x):
   for i in range(2,x):
       if x%i==0:
          return False
   return True

def printPFactors(n):
    for i in range(2, n+1):
        if isPrime(i):
           x=i
           while n%x==0:
               print(i)
               x=x*i
n=int(input("Enter n:"))
printPFactors(n)

Output:
Enter n:100
2
2
5
5

First we obtain the user’s input, then the function is called and the input number is passed to it. When the function is called it runs a loop from 2, and increment of 1 by every step of the loop.

If it is prime we check how many times the number divides the input number in the second function, thus we have seen how we can obtain prime factors in Python. In the next article, we will look at Strings in Python and their usage.

Leave a Comment