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

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

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