0 
def all_primes(start,end):
    list_nonprimes = []
    list_primes = []

    for i in range(start,end):
        for a in range(2,i):
            if i % a == 1 and i not in list_nonprimes:
                if i not in list_primes:
                    list_primes.append(i)
            else:
                list_nonprimes.append(i)

    return list_primes

为什么这会给我一个不正确的输出？

>>> all_primes(1,10)
[3,5,7,9]

如何消除9？

4

3 回答 3

4

有一种更直接的方法可以做到这一点，因为您已经固有地生成了少于您当前检查的数字的素数列表：

def all_primes(start,end):
    list_primes = []

    for i in range(2,end):
        for a in list_primes:
            if i % a == 0:
                break
        else:
            list_primes.append(i)

    return [x for x in list_primes if x >= start]

理解这一点的关键是了解该for...else构造在 Python 中是如何工作的。本质上，for循环可以有一个语句，只有在循环评估期间没有运行else任何语句时才会执行该语句。break

于 2012-11-17T05:42:33.903 回答
0

将其更改为：

        if i % a == 1 and i not in list_nonprimes:
            if i not in list_primes:
                list_primes.append(i)
        else:
            list_nonprimes.append(i)

到：

        if i % a == 0 and i not in list_primes:
            if i not in list_nonprimes:
                list_nonprimes.append(i)
        else:
            list_primes.append(i)

旁白：您也可以考虑实施埃拉托色尼筛法。这很容易理解并且效率更高。

于 2012-11-17T05:35:27.537 回答
0

我尝试检查您的代码以查看您哪里出错了，但最终进行了一些更改和优化。我已经评论了代码，所以希望它能够自我解释。

def all_primes(start,end):
    list_nonprimes = []
    list_primes = []

    for i in range(start,end):
        # if already present in non_primes, skip
        if i in list_nonprimes: continue

        # if already present in primes, skip
        if i in list_primes: continue

        # if 2, mark it as prime. Special case
        if i == 2 :
            list_primes.append(i)
            continue

        # even numbers are not prime
        if i%2 == 0: 
            list_nonprimes.append(i)
            continue

        # only check divisibility with odd numbers starting at 3
        # and ending at sqrt(i)
        for a in range(3,int(i**0,5)+1,2):
            if i % a == 0 :
                list_nonprimes.append(i)
                break

        # if we got here, and the number wasn;t added to non_primes
        # it must be a prime
        if i not in list_nonprimes: list_primes.append(i)            

    return list_primes

start = 2
end = 10
print all_primes(start, end)

演示

于 2012-11-17T05:42:40.527 回答