为什么我的阿特金筛法实施忽略了接近指定限制的数字?
-
25-09-2019 - |
题
我的实施 阿特金筛 要么忽略极限附近的素数,要么忽略极限附近的复合数。有些限制有效,有些则无效。我完全不知道出了什么问题。
def AtkinSieve (limit):
results = [2,3,5]
sieve = [False]*limit
factor = int(math.sqrt(lim))
for i in range(1,factor):
for j in range(1, factor):
n = 4*i**2+j**2
if (n <= lim) and (n % 12 == 1 or n % 12 == 5):
sieve[n] = not sieve[n]
n = 3*i**2+j**2
if (n <= lim) and (n % 12 == 7):
sieve[n] = not sieve[n]
if i>j:
n = 3*i**2-j**2
if (n <= lim) and (n % 12 == 11):
sieve[n] = not sieve[n]
for index in range(5,factor):
if sieve[index]:
for jndex in range(index**2, limit, index**2):
sieve[jndex] = False
for index in range(7,limit):
if sieve[index]:
results.append(index)
return results
例如,当我生成极限为 1000 的素数时,阿特金筛会错过素数 997,但包含合数 965。但如果我生成的限制达到 5000,它返回的列表是完全正确的。
解决方案
- 改变
lim
到limit
. 。当然你一定知道这一点。 - 自从
sieve = [False]*limit
,允许的最大索引是limit-1
.然而,在这条线上
if (n <= limit) and (n % 12 == 1 or n % 12 == 5):
你正在检查是否
n<=limit
. 。如果n==limit
然后sieve[n]
引发 IndexError。使用较小的值尝试您的算法limit
(例如。n=50)。你会看到这个错误出现。一个简单的解决方法是使用sieve = [False]*(limit+1)
这个简单的修复有点浪费,因为 sieve[0] 从未被使用过。所以你可能认为更好的解决方法是保留
sieve = [False]*limit
, ,但通过逐步索引来修复所有其他代码sieve
下降了一位。(例如,改变sieve[n]
到sieve[n-1]
到处等等)但是,这将迫使您进行一些额外的减法,这对速度不利。因此,简单/浪费的解决方案实际上可能是更好的选择。 - 根据 http://en.wikipedia.org/wiki/Sieve_of_Atkin,x应该是[1,sqrt(limit)]的整数,包括端点。
在你的代码中
factor = int(math.sqrt(limit))
和
int
采取 地面 的math.sqrt(limit)
. 。此外,range(1,factor)
从 1 到因子 1。所以你落后了 1。所以你需要将其更改为
factor = int(math.sqrt(limit))+1
- 看 列出 N 以下所有素数的最快方法 由 Steve Krenzel 提供的阿特金筛法的替代(且更快)实现。
def AtkinSieve (limit):
results = [2,3,5]
sieve = [False]*(limit+1)
factor = int(math.sqrt(limit))+1
for i in range(1,factor):
for j in range(1, factor):
n = 4*i**2+j**2
if (n <= limit) and (n % 12 == 1 or n % 12 == 5):
sieve[n] = not sieve[n]
n = 3*i**2+j**2
if (n <= limit) and (n % 12 == 7):
sieve[n] = not sieve[n]
if i>j:
n = 3*i**2-j**2
if (n <= limit) and (n % 12 == 11):
sieve[n] = not sieve[n]
for index in range(5,factor):
if sieve[index]:
for jndex in range(index**2, limit, index**2):
sieve[jndex] = False
for index in range(7,limit):
if sieve[index]:
results.append(index)
return results
不隶属于 StackOverflow