100011322432435545
May 18, 2021
I had an email from a reader who found my factoring program on Stack Overflow:
Python 2.7.13 (default, Mar 13 2017, 20:56:15) [GCC 5.4.0] on cygwin Type "help", "copyright", "credits" or "license" for more information. >>> def isPrime(n, k=5): # miller-rabin ... from random import randint ... if n < 2: return False ... for p in [2,3,5,7,11,13,17,19,23,29]: ... if n % p == 0: return n == p ... s, d = 0, n-1 ... while d % 2 == 0: ... s, d = s+1, d/2 ... for i in range(k): ... x = pow(randint(2, n-1), d, n) ... if x == 1 or x == n-1: continue ... for r in range(1, s): ... x = (x * x) % n ... if x == 1: return False ... if x == n-1: break ... else: return False ... return True ... >>> def factors(n, b2=-1, b1=10000): # 2,3,5-wheel, then rho ... def gcd(a,b): # euclid's algorithm ... if b == 0: return a ... return gcd(b, a%b) ... def insertSorted(x, xs): # linear search ... i, ln = 0, len(xs) ... while i < ln and xs[i] < x: i += 1 ... xs.insert(i,x) ... return xs ... if -1 <= n <= 1: return [n] ... if n < -1: return [-1] + factors(-n) ... wheel = [1,2,2,4,2,4,2,4,6,2,6] ... w, f, fs = 0, 2, [] ... while f*f <= n and f < b1: ... while n % f == 0: ... fs.append(f) ... n /= f ... f, w = f + wheel[w], w+1 ... if w == 11: w = 3 ... if n == 1: return fs ... h, t, g, c = 1, 1, 1, 1 ... while not isPrime(n): ... while b2 <> 0 and g == 1: ... h = (h*h+c)%n # the hare runs ... h = (h*h+c)%n # twice as fast ... t = (t*t+c)%n # as the tortoise ... g = gcd(t-h, n); b2 -= 1 ... if b2 == 0: return fs ... if isPrime(g): ... while n % g == 0: ... fs = insertSorted(g, fs) ... n /= g ... h, t, g, c = 1, 1, 1, c+1 ... return insertSorted(n, fs)
He complained that the program failed to factor the number 100011322432435545, entering an infinite loop instead of returning a list of factors.
Your task is to figure out what is wrong, and fix it. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.