0

この関数は、数が素数であるかどうかを確認するために作成しました。それ自体は正常に動作しているようですが、別の関数で使用すると動作しないようです。

これが私のIsPrime関数です。

def is_prime(n):
    boolean = False
    if n == 2 or n == 3:
            return True
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True

以下の関数は、2000000未満のすべての素数の合計を計算します。

def problem10(prime, result):
    if prime > 2000000:
        return 
    if is_prime(prime):
        print 'prime is ', prime 
        result = result + prime
        problem10(prime + 1, result)
    return result

どこが間違っているのか理解できません。

コメントをいただければ幸いです。

4

6 に答える 6

6

is_prime偶数をチェックしていません。たとえば、4 を渡した場合、それが 2 でも 3 でもないことがわかり、1 回実行されるループに進み、3 で割り切れるかどうか (割り切れない) をチェックします。ループを終了するとTrue、4 が実際には素数ではないことがわかっている場合、 が返されます。

于 2012-09-19T20:30:41.777 に答える
3

関数の流れにバグがありますproblem10。problem10要するに、再帰関数の結果値を実際には使用していないという事実です。コードを次のようにする必要があります (再帰を維持したい場合は、代わりにループを検討することをお勧めします)。

def problem10(prime):
    """ calculates the sum of primes from this prime until 2000000 (2 * 10**6) """
    if prime >= 2000000:
       return 0
    elif is_prime(prime):
       return prime + problem10(prime + 1)
    else:
       return problem10(prime + 1)

この関数アプローチには、考慮すべき重要なポイントがいくつかあることに注意してください。

  1. 素数 >= 2000000 の場合、この関数は空の合計を表します。したがって、0 を返します。
  2. is_prime(prime) の場合、この関数は合計に素数を追加する必要があります
  3. それ以外の場合、合計は次の数からの素数の合計と同じです (素数ではないため、とにかく小さい数を除外する必要があるため)。

  4. 元の試みと比較して、 return ステートメントで式を使用すると、関数のロジック (フロー) が大幅に簡素化されることに注意してください。それは本当にはるかに読みやすいです。また、次の理由により、元の関数が機能しなかったことに注意してください。

    を。あなたの関数は実行中の合計（結果）を更新しません

    b. たとえそうだったとしてもNone、元の関数が素数>= 2000000の場合に何も返さなかったため、最終的に何かに追加することになります。

于 2012-09-19T20:42:37.303 に答える
1

is_prime関数の正しいバージョンを次に示します。これは、2による試行除算と、3からnの平方根までの奇数を使用して、nが素数であるか複合であるかを判別します。

def is_prime(n):
    if n % 2 == 0:
        return n == 2
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2
    return True

この問題を解決するためのより良い方法は、エラトステネスのふるいを使用して2000000未満のすべての素数を識別し、それらを合計することです。エラトステネスの簡単なふるいは次のとおりです。

def sieve(n):
    b, p, ps = [True] * (n+1), 2, []
    for p in xrange(2, n+1);
        if b[p]:
            ps.append(p)
            for i in xrange(p+p, n+1, p):
                b[i] = False
    return ps

数が素数であるか合成数であるかを判断し、すべての素数のリストを生成するためのより良い（より速い）方法がありますが、これらはあなたのタスクには十分です。

于 2012-09-19T22:15:20.920 に答える
1

より高速な素数リストは次のようになります。

import numpy as np

def primesfrom2to(n):
    """ Returns a array of primes, p < n """
    assert n>=2
    sieve = np.ones(n/2, dtype=np.bool)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]:
            sieve[i*i/2::i] = False
    return np.r_[2, 2*np.nonzero(sieve)[0][1::]+1]

次に、その合計：

print sum(primesfrom2to(2000000))

関数を使用する場合は、次のように書き直すことをお勧めします。

def is_prime(n):
    if n in (2,3):
        return True
    if not n%2:
        return False        
    if any(n%x == 0 for x in xrange(3, int(n**0.5)+1, 2)):     
        return False   
    return True
于 2012-09-19T21:45:19.210 に答える
0 
def isPrime(num,div=2):
if(num==div):
    return True
elif(num % div == 0):
    return False
else:
    return isPrime(num,div+1)
于 2014-02-20T09:58:42.250 に答える
0

そのように範囲をチェックする必要がありますか

for x in range(2, sqrt(n)+1):
    if n % x == 0:
        return False

平方根よりも大きい根はありません。

于 2012-09-19T20:31:59.497 に答える