Integer Factorization

Overview

Given a composite integer $n$, 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 < n$ such that $p|n$or programmatically n%p==0

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

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

Now taking a better look at it, one would realize that a factor of $n$can't be bigger than $\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.