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

コードを調べてどこが間違っているかを確認しようとしましたが、かなりの変更と最適化を行うことになりました。コードにコメントしたので、うまくいけばそれ自体が説明されます。

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 に答える
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 に答える