Different Ways of Prime Factoring a Number with Python: Analysis and Comparison.

Prime numbers, and prime factorization, are interesting part of mathematics they are so simple, yet humans are unable to discover to a concrete pattern in them, but what we can do is calculate these, in this passage I will go into three ways one can prime-factorize number using python, the first two of which are feasible and practical.

The first way is only too simple:

Iterate through all the numbers between 2 and the number in question, if n is fully divisible by one of them, say that it is a non-prime number, or else it is a prime.

#!/usr/bin/env python3

a= int(input())
for i in range (2,a):
	if a%i==0:
		for j in range(2,i):
			if(i%j==0):
				break
			if(j==i-1):
				t=a
				while(1):
					print(i)
					t/=i
					if(t%i!=0):
						break
		

Surprisingly, there is not much optimization we can do on this. we could have it literate only between 2 and square root of the number to decrease the run time and end up with this function

import math
def printFactors(a):
	for i in range (2,int(math.sqrt(a))):
		if a%i==0:
			for j in range(2,i):
				if(i%j==0):
					break
				if(j==i-1):
					t=a
					while(1):
						print(i)
						t/=i
						if(t%i!=0):
							break
					i=int(t)
					t=a
					while(1):
						print(i)
						t/=i
						if(t%i!=0):
							break
						
#printFactors(63)

That’s it. That is as much optimization as we can get.

The underlying math be hind this is that the array of prime numbers have been mathematically proved to be infinitely long, but it has not proven possible to formulate the general term, in other words, reliably calculate the next prime number from a particular prime number without iterating. Interestingly, such a task has not been proven impossible either.

Wait, there is a different approach, a shortcut – Pre-processing!

This is essentially cheating the system in pre-calculating what numbers are prime and what are not, then writing them into a table, eventually just reading the table for a given input. The programs look like such.

What do you say?

There is a far more interesting way of factorizing a number, and it is genuinely scary. The algorithm is called Shor’s Algorithm, and it has a lot to do with quantum computing and cryptography. This is a simple implementation of the algorithm below. I will not be explaining its relationship to the areas list above because that is beyond the scope of this blog, but I will link my related blogs below for ease reference, check them out if you are interested in this algorithm or any of these related fields mentioned.

https://github.com/toddwildey/shors-python/blob/master/shors.py