Here is an algorithm, written in Python, to factorize integers, using backtracking. The time consumption should be aroundÂ .

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