哇哦，
遇到以下问题，我无法解决。 处理长度在 5 - 52 左右的数字，我不想得到它们的质因数。 使用Python，我发现了以下两种算法：
我。
def faktorisiere(n):
l = [] # Lösungsmenge
# Auf Teilbarkeit durch 2, und alle ungeraden Zahlen von 3..n/2 testen
for i in chain([2], range(3, n//2 + 1, 2)):
# Ein Teiler kann mehrfach vorkommen (z.B. 4 = 2 * 2), deswegen:
while n % i == 0:
l.append(i)
print(i)
n = n // i # "//" ist ganzzahlige Division und entspricht int(n/i)
if i > n: # Alle Teiler gefunden? Dann Abbruch.
break
print(l)
二.
x = input("Number: ")
mode = x[-1:]
x = int(x[:-1])
if int(x) < 1000000000000:
faktorisiere(x)
else:
if mode == 'f':
faktorisiere(x)
rx = int(sqrt(x)) + 1
for i in range(1, rx+1):
if mode == 'a':
if x % i == 0:
y = int(x/i)
print(str(x), "=", i, "*", str(y))
if mode == 'u':
if i % 2 != 0:
if x % i == 0:
y = int(x/i)
print(str(x), "=", i, "*", str(y))
但是第一个代码计算如下数字的速度非常慢： 1917141215419419171412154194191714
第二个工作速度更快一些，但我得到了错误的输出，而且我无法在代码中找到错误。 我们以给定的数字为例。 这些是 python 输出的第一行：
1917141215419419171412154194191714 = 1 * 1917141215419419143900621852114944
1917141215419419171412154194191714 = 2 * 958570607709709571950310926057472
但是正如您所看到的，这些乘法并不等于结果。 代码有错误吗？ 或者只是因为数字的长度？ 希望你能帮助我。
最美好的祝愿， 时代人
您需要一种比试除法更好的算法来分解您正在使用的大小的数字。 John Pollard 的 rho 算法是试除法的一个简单步骤：
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)
...
>>> factors(1917141215419419171412154194191714)
[2, 3, 13, 449941L, 54626569996995593878495243L]
分解立即返回。请参阅此处了解其工作原理的说明。要分解更大的数字，您需要查看诸如椭圆曲线法或二次筛法之类的算法，但请注意这两种算法都很复杂。
Python 3 编辑@user448810 的答案：
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)
print(factors(1917141215419419171412154194191714))