Eratosthenes 筛法返回不正确的答案

Question

我是一个初学者，试图创建一个函数来确定一个值是否为质数。

def isPrime(number):
    marked = [] ## create empty list
    for i in xrange(2, number+1):
        if i not in marked: ## begin loop to remove multiples of i in list
            for j in xrange(i * i, number + 1, i):
                marked.append(j)
            if i == number: ## I'm assuming that if 
            ##the program made it here, i is not in marked.

print isPrime(7)
>>> True
print isPrime(10)
>>> None ## This should be False...ok so I tried to tinkering here.

所以我试图解决这个问题是将最后一个条件编辑为：

if i == number:
    return True
else: ## Begin new line of code to correct for false positive
    return False

这条额外的线弄乱了一切，因为它现在显示：

isPrime(7)
>>> False

EDIT 结果证明这个方法是完全错误的方法。所以根据 Jean-Francois 的评论，这是一种更简单的检查素数的方法

def is_prime(n):
    if n<2:
       return False  # handle special case
    sn = int(n**0.5)+1
    for i in range(2,sn):
        if n%i==0:
            return False
    return True

直觉：

假设我们要检查 61 是否是素数。

我们知道任何小于 2 的都不可能是质数，所以这个代码有一个 n<2 排除这种可能性。
我们知道61的平方根大约是7.8，这也意味着如果 61 不是素数，我们就排除了因子为 8 或任何大于 8 的因子。

所以剩下要测试的是 2 到 7 之间的所有东西。如果 2 到 7 之间的所有东西都看它们是否是 61 的因数并且它们仍然失败，这意味着我们知道这个数字是质数。

Answer 1

即使这不是什么新鲜事，我也会回答这个问题。它回答了问题，给出了 2 种工作方式并在 python 中进行了测试。应该是主题。

首先，每次都计算筛子来测试一个数字是非常低效的。如果你有很多数字要测试，那就是这样。一个工作版本（python 2 & 3 兼容），由我改编自一些 Project Euler 解决方案

def primes(n):
    """Generate a list of the prime numbers [2, 3, ... m] where
    m is the largest prime <= n."""
    n += 1
    sieve = list(range(n))
    sieve[:2] = [0, 0]
    for i in range(2, int(n**0.5)+1):
        if sieve[i]:
            for j in range(i**2, n, i):
                sieve[j] = 0
    # Filter out the composites, which have been replaced by 0's
    return [p for p in sieve if p]

测试：

print(primes(100))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

要测试特定数字，请改为执行此操作

def is_prime(n):
    if n<2:
       return False  # handle special case
    sn = int(n**0.5)+1  # +1 because of perfect squares like 49
    for i in range(2,sn):
        if n%i==0:
            return False
    return True

Eratosthenes 筛法返回不正确的答案

Sieve of Eratosthenes returning incorrect answers

python

primes

if-statement

boolean

sieve-of-eratosthenes

直觉：