# A Silly Algorithm for Prime Factorization

Standard practice algorithms for prime factorization of a integer n known to be composite of two primes, p and q, use the *modular* structure of integers to attempt to do prime factorization. We present a very simple and intuitive algorithm for prime factorization on a simpler premise, that n is the product of two integers and only two integers. Note that p > sqrt(n) WLOG.

p = sqrt(n)

q = n / p

num_runs = 0while abs(int(p) - p) > 0 and abs(int(q) - q) > 0:

if num_runs % 2 == 0

p = ceil(p)

q = n / p

else

q = floor(q)

p = n / q

num_runs += 1

return p, q

Potentially, the residues can be exploited to speed up this silly algorithm.