# Integer Factorization Using Backtracking

By | February 1, 2016

Here is an algorithm, written in Python, to factorize integers, using backtracking. The time consumption should be aroundÂ  $\mathcal O 2 ^ {\frac n 2}$.
So it's not the fastest one, but it's nice.
To use it, save the code to a file. If you call the file, for example, "factorize.py", then run

python factorize.py <integer to factorize>


Have fun!


import sys
def getbit(i,n):
return (i>>n)&1

def setbit(i,n,val=1):
if val==1:
return i | (1<<n)
return i & (~(1<<n))

def bitcmp(i1,i2,n):
for i in range (0,n):
b2 = getbit(i2,i)
b1 = getbit(i1,i)
if b1!=b2:
return b1-b2
return 0

def fac_check(i,i1,i2,bits):
p = i1*i2
if p>i:
return -3
if p==i:
if i1==1 or i2==1:
return -4
return 10
return bitcmp(i,p,bits)

def factorize_run(i,i1,i2,n):
for b in range (0,4):
i1 = setbit(i1,n,getbit(b,0))
i2 = setbit(i2,n,getbit(b,1))
rc = fac_check(i,i1,i2,n+1)
if rc==10:
return factorize(i1)+factorize(i2)
if rc==0:
f = factorize_run(i,i1,i2,n+1)
if f!=[i]:
return f
return [i]

def factorize(i):
l = factorize_run(i,0,0,0)
l.sort()
return l

fpr = int(sys.argv[1])

print "Factorizing "+str(fpr)+" ..."
rc = factorize(fpr)
print rc