經過很長一段時間的休息后，我又回到了編程領域，所以請原諒任何愚蠢的錯誤/低效的代碼。我正在創建一個使用 RSA 加密方法的加密程序，該方法涉及查找數字的互質來生成密鑰。我使用歐幾里得算法生成最大公因數，然后如果 HCF == 1，則將互質添加到列表中。我為不同的數字生成兩個互質列表，然后進行比較以找到兩個集合中的互質?；敬a如下：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在計算數十億范圍內的極大數字時，這對于中等級別的安全性也是必要的。我認為這是一個內存問題，但我無法弄清楚如何以非內存密集型方式執行此操作。我嘗試了多處理，但這只是使我的計算機由于運行的進程數量而無法使用。如何計算大數的互質，然后以有效且可行的方式比較兩組互質？
2 回答
慕后森
TA貢獻1802條經驗 獲得超5個贊
如果您唯一擔心的是內存不足，您可以使用生成器。
def coprimes(n):
? ? for i in range(1,n):
? ? ? ? if gcd(i, n) == 1:
? ? ? ? ? ? yield i
這樣您就可以使用互質值，然后在不需要時將其丟棄。然而，沒有什么可以改變你的代碼是 O(N^2) 并且對于大素數總是執行緩慢的事實。這假設歐幾里得算法是恒定時間的，但事實并非如此。
小怪獸愛吃肉
TA貢獻1852條經驗 獲得超1個贊
您可以改變策略并從共同素因數的角度來解決這個問題。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
添加回答
舉報
0/150
提交
取消