素数分解一个3000位数，最大素数<=104743 (6位)-这能在一台“正常”计算机上在几分钟内完成吗？
素数分解一个3000位数，最大素数<=104743 (6位)-这能在一台“正常”计算机上在几分钟内完成吗？
提问于 2020-04-05 13:10:16
我有一个3000位长数字，它的素数必须考虑在内。我知道没有比104743更大的素因子。
在一台“正常”电脑上能在几分钟内做到这一点吗?因为最高的因素是相对较低的？
作为参考，我尝试了我在这里找到的代码。
def factorize(n):
count = 0;
while ((n % 2 > 0) == False):
# equivalent to n = n / 2;
n >>= 1;
count += 1;
# if 2 divides it
if (count > 0):
print(2, count);
# check for all the possible
# numbers that can divide it
for i in range(3, int(math.sqrt(n)) + 1):
count = 0;
while (n % i == 0):
count += 1;
n = int(n / i);
if (count > 0):
print(i, count);
i += 2;
# if n at the end is a prime number.
if (n > 2):
print(n, 1);
n = 5*7*11*13*17*19*23*29*31*37*41*43*47;
factorize(n);
# This code is contributed by mits 这个代码用59秒来制造一个18位数的数字，其中47是最高的因素(102481630431415235是“测试号”)。如果我停留在第47因子，它只使用31秒，但它仍然是太长，因为测试数字远低于我的需要。
回答 1
Stack Overflow用户
回答已采纳
发布于 2020-04-05 13:48:23
因为素数相对较小，所以我认为，如果您可以先使用generate the list of primes并使用它们进行因式分解，那么速度会更快。
下面是一个示例代码：
import math
# Copied from https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n/3035188#3035188
def primes2(n):
""" Input n>=6, Returns a list of primes, 2 <= p < n """
n, correction = n-n%6+6, 2-(n%6>1)
sieve = [True] * (n//3)
for i in range(1,int(n**0.5)//3+1):
if sieve[i]:
k=3*i+1|1
sieve[ k*k//3 ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]
def factorize2(n, primes):
factors = {}
cur_num = n
for p in primes:
if p*p > cur_num:
break
while cur_num % p == 0:
cur_num //= p
factors[p] = factors.get(p, 0) + 1
if cur_num >= 2:
factors[cur_num] = factors.get(cur_num, 0) + 1
return factors
# Precompute the primes
primes = primes2(110000)
n = 5*7*11*13*17*19*23*29*31*37*41*43*47
result = factorize2(n, primes)
print(result)对于示例中的数字，此代码运行大约50 in (这比您问题中的代码要快得多)。
更新：
我试用了3000位数字，密码如下：
def generate_big_num(primes, th):
import random
num = 1
while num < th:
num *= random.choice(primes)
return num
th = 10**3000
big_num = generate_big_num(primes, th)
print(big_num)
result = factorize2(big_num, primes)
print(result)在我的笔记本上只用了大约60毫秒。所以你的问题的答案是是！
希望这能有所帮助！
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/61043121
复制相关文章
相似问题
腾讯云开发者
