Integer Factorization


Given a composite integer nn, can it be decomposed as a product of smaller integers (hopefully as a unique product of prime factors)?

As easy as it may sound, integer factorization in polynomial time on a classical computer stands one of the unsolved problems in computation for centuries!

Lets start dumb, all we need to do is check all the numbers 1<p<n1 < p < n such that pnp|nor programmatically n%p==0

def factors(n):
divisors = []
for p in range(1,n):
if n%p==0:
return divisors

Seems like its an O(n)O(n)algorithm! whats all the deal about? By polynomial time, we mean polynomial time in bbwhen nnis a b-bit number, so what we looking at is actually a O(2b)O(2^b)which is actually exponential (which everyone hates)

Now taking a better look at it, one would realize that a factor of nncan't be bigger than n\sqrt{n} Other observation would be, if we already checked a number (say 2) to not be a divisor, we dont need to check any multiple of that number since it would not be a factor.