如何停止循环内存不足？

Question

经过很长一段时间的休息后，我又回到了编程领域，所以请原谅任何愚蠢的错误/低效的代码。我正在创建一个使用 RSA 加密方法的加密程序，该方法涉及查找数字的互质来生成密钥。我使用欧几里得算法生成最大公因数，然后如果 HCF == 1，则将互质添加到列表中。我为不同的数字生成两个互质列表，然后进行比较以找到两个集合中的互质。基本代码如下：def gcd(a, b):    while b:        a,b=b,a%b    return adef 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):

    p = 2

    while p*p<=N:

        count = 0

        while N%p == 0:

            count += 1

            N //= p

        if count: yield p

        p += 1 + (p&1)

    if N>1: yield N

import math

def compare2(n,m):

    # skip list for multiples of common prime factors

    skip = { p:p for p in primeFactors(math.gcd(n,m)) } 

    for x in range(1,min(m,n)):

        if x in skip:

            p = skip[x]                 # skip multiple of common prime

            m = x + p                   # determine next multiple to skip

            while m in skip: m += p     # for that prime

            skip[m] = p

        else:

            yield x                     # comon coprime of n and m 

性能比匹配互质列表要好得多，尤其是在较大的数字上：

from timeit import timeit

timeit(lambda:list(compare2(10**5,2*10**5)),number=1)

# 0.025 second

timeit(lambda:list(compare2(10**6,2*10**6)),number=1)

# 0.196 second

timeit(lambda:list(compare2(10**7,2*10**7)),number=1)

# 2.18 seconds

timeit(lambda:list(compare2(10**8,2*10**8)),number=1)

# 20.3 seconds

timeit(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 math

def compare3(n,m):

    d = math.gcd(n,m)

    for c in range(1,min(n,m)):

        if math.gcd(c,d) == 1:

            yield c

timeit(lambda:list(compare3(10**6,2*10**6)),number=1)

# 0.28 second

timeit(lambda:list(compare3(10**7,2*10**7)),number=1)

# 2.84 seconds

timeit(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