时间戳

首页 > 解决方案 > 为什么即使我使用了eratosthenes筛并且我还使用集合而不是列表，我的素数代码也不适用于大数？

python - 为什么即使我使用了eratosthenes筛并且我还使用集合而不是列表，我的素数代码也不适用于大数？

问题描述

我的代码：

import math
n=int(input('Enter the number'))
b=list(range(2,n+1))
for i in range(2,int(math.sqrt(n))+1):
    for j in b:
        if j!=i and j%i==0:
            b[b.index(j)]=0

b={i for i in b if not i==0}
c={i for i in b if n%i==False}
print(b)
print(c)

这一个，我以自己的方式实施了筛子。为什么它不适用于数字 600851475143 的 Project Euler 问题 3？我正进入（状态：

Enter the number600851475143
Traceback (most recent call last):
  File "C:/Users/raja/AppData/Local/Programs/Python/Python37-32/ui.py", line 6, in <module>
    b=list(range(2,n+1))
OverflowError: Python int too large to convert to C ssize_t

我只是一个初学者和自学成才。我欢迎所有简单的建议，请以善意的方式指出我的错误:)。谢谢你。

标签： pythonpython-3.xsetsieve-of-eratosthenes

解决方案

埃拉托色尼筛法用于查找给定范围内的所有素数，查找时间恒定，空间和时间复杂度为 o(n)。因此，当您需要检查许多数字的主要条件时，最好使用它。由于空间复杂度为 o(n)，因此对于高数，它需要巨大的空间。

如果您需要检查一次素数，那么最好使用 o(n) 时间复杂度和 o(1) 空间复杂度即时计算它。

推荐阅读