如何停止循环内存不足？

Question

经过很长一段时间的休息后，我又回到了编程领域，所以请原谅任何愚蠢的错误/低效的代码。

我正在创建一个使用 RSA 加密方法的加密程序，该方法涉及查找数字的互质来生成密钥。我使用欧几里得算法生成最大公因数，然后如果 HCF == 1，则将互质添加到列表中。我为不同的数字生成两个互质列表，然后进行比较以找到两个集合中的互质。基本代码如下：

def gcd(a, b):

    while b:

        a,b=b,a%b

    return a

def coprimes(n):

    cp = []

    for i in range(1,n):

        if gcd(i, n) == 1:

            cp.append(i)

    print(cp)

def compare(n,m):

    a = coprimes(n)

    b = coprimes(m)

    c = []

    for i in a:

        if i in b:

            c.append(i)

    print(c)

该代码非常适合小数字，并为我提供了我想要的东西，但执行需要很长时间，并且最终Killed在计算数十亿范围内的极大数字时，这对于中等级别的安全性也是必要的。我认为这是一个内存问题，但我无法弄清楚如何以非内存密集型方式执行此操作。我尝试了多处理，但这只是使我的计算机由于运行的进程数量而无法使用。

如何计算大数的互质，然后以有效且可行的方式比较两组互质？

Answer 1

如果您唯一担心的是内存不足，您可以使用生成器。def coprimes(n):    for i in range(1,n):        if gcd(i, n) == 1:            yield i这样您就可以使用互质值，然后在不需要时将其丢弃。然而，没有什么可以改变你的代码是 O(N^2) 并且对于大素数总是执行缓慢的事实。这假设欧几里得算法是恒定时间的，但事实并非如此。

Answer 2

您可以改变策略并从共同素因数的角度来解决这个问题。n 和 m 之间的公共互质将是不能被任何公共质因数整除的所有数字。def primeFactors(N):&nbsp; &nbsp; p = 2&nbsp; &nbsp; while p*p<=N:&nbsp; &nbsp; &nbsp; &nbsp; count = 0&nbsp; &nbsp; &nbsp; &nbsp; while N%p == 0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count += 1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; N //= p&nbsp; &nbsp; &nbsp; &nbsp; if count: yield p&nbsp; &nbsp; &nbsp; &nbsp; p += 1 + (p&1)&nbsp; &nbsp; if N>1: yield Nimport mathdef compare2(n,m):&nbsp; &nbsp; # skip list for multiples of common prime factors&nbsp; &nbsp; skip = { p:p for p in primeFactors(math.gcd(n,m)) }&nbsp;&nbsp; &nbsp; for x in range(1,min(m,n)):&nbsp; &nbsp; &nbsp; &nbsp; if x in skip:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; p = skip[x]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;# skip multiple of common prime&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; m = x + p&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;# determine next multiple to skip&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while m in skip: m += p&nbsp; &nbsp; &nbsp;# for that prime&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; skip[m] = p&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield x&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;# comon coprime of n and m&nbsp;性能比匹配互质列表要好得多，尤其是在较大的数字上：from timeit import timeittimeit(lambda:list(compare2(10**5,2*10**5)),number=1)# 0.025 secondtimeit(lambda:list(compare2(10**6,2*10**6)),number=1)# 0.196 secondtimeit(lambda:list(compare2(10**7,2*10**7)),number=1)# 2.18 secondstimeit(lambda:list(compare2(10**8,2*10**8)),number=1)# 20.3 secondstimeit(lambda:list(compare2(10**9,2*10**9)),number=1)# 504 seconds在某些时候，构建所有互质列表会成为瓶颈，您应该在它们从生成器中出来时使用/处理它们（例如计算有多少个）：timeit(lambda:sum(1 for _ in compare2(10**9,2*10**9)),number=1)# 341 seconds解决这个问题的另一种方法是列出 n 和 m 之间的 gcd 的互质数，该方法比质因数方法慢一些，但编码更简单：import mathdef compare3(n,m):&nbsp; &nbsp; d = math.gcd(n,m)&nbsp; &nbsp; for c in range(1,min(n,m)):&nbsp; &nbsp; &nbsp; &nbsp; if math.gcd(c,d) == 1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield ctimeit(lambda:list(compare3(10**6,2*10**6)),number=1)# 0.28 secondtimeit(lambda:list(compare3(10**7,2*10**7)),number=1)# 2.84 secondstimeit(lambda:list(compare3(10**8,2*10**8)),number=1)# 30.8 seconds鉴于它不使用内存资源，因此在某些情况下可能是有利的：timeit(lambda:sum(1 for _ in compare3(10**9,2*10**9)),number=1)# 326 seconds