0

指定された値未満の素数の数とすべての素数の値を返す Python 関数を作成しようとしています。エラトステネスのふるいアルゴリズムを使用する必要があります。関数に何かが欠けていると思います-たとえば、100未満の素数を見つけたい場合。得られるのは2、3、5、7だけです。「平方根」を使用しない場合は認識しています、必要なすべての素数を取得できます。しかし、そこに平方根を含める必要があると言われました。誰かが私のコードを見て、私が欠けているものを教えてもらえますか? 御時間ありがとうございます。

def p(n):
is_p=[False]*2 + [True]*(n-1)
for i in range(2, int(n**0.5)):
    if is_p[i]:
        yield i
        for j in range(i*i, n, i):
            is_p[j] = False
4

3 に答える 3

4

「平方根を使用する必要があると言われました」。それはなぜだと思いますか。通常、E. のふるいは、すべての「非素数」数をリストから削除するために使用されます。これを行うには、素数を見つけて、リスト内のその素数の倍数をすべてチェックします。次の「チェックされていない」数字はあなたの次の素数です - あなたはそれを（でyield）報告してから、もう一度チェックを続けます。平方根より小さい因数だけをチェックする必要があります。平方根より大きい因数には平方根より小さい対応する因数があるため、それらはすでに見つかっています。

残念ながら、素数の出力に関しては、「途中で止める」ことはできません。たとえば、101素数です。しかし、11 までしかループしないと、そこにあることに決して気付かないでしょう。したがって、次の 2 つの手順が必要です。

1）すべての「可能な倍数」をループします-ここでは「平方根までのみ」行くことができます

2) チェックされていないすべての番号のリストをチェックします。ここでは、「最後まで行く」必要があります。

これにより、次のコードが作成されます。

def p(n):
  is_p=[False]*2 + [True]*(n-1)
  for i in range(2, int(n**0.5)):
    if is_p[i]:
        for j in range(i*i, n, i):
            is_p[j] = False
  for i in range(2, n):
    if is_p[i]:
      yield i

print list(p(102))

結果は までの素数のリストです101。

于 2013-06-27T22:16:18.643 に答える
2

forループを除いて、ロジックは正しいです。に達したら終了しsqrt(n)-1ます。の場合p(100)、2 から 9 までしか実行されません。したがって、素数は 9 までしか得られません。

于 2013-06-27T22:09:17.083 に答える