我下面的方法是超级复制粗糙和超级复制缓慢。任何关于优化建议的提示。我知道对于两个不同素数的半素数,其数小于或等于半素数的一半。但我不知道如何更有效地检查大量素数的列表。当我的13位数或者更大的时候。在
import math
def eratosthenes(n):
multiples = set()
primes = set()
for i in range(2, n+1):
if i not in multiples:
if i <= math.ceil(math.sqrt(n)+10):
primes.add(i)
for j in range(i*i, n+1, i):
multiples.add(j)
result = []
for p in primes:
while n % p == 0: # while p divide n...
result.append(p)
n = n // p
if n <= 1:
break
对于较大的素数,可以尝试用simple来实现Pollard's rho algorithm
这应该在合理的时间内对20位数字有效。在
相关问题 更多 >
编程相关推荐