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，然后继续执行循环，该循环将执行一次，检查它是否能被 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 语句中使用表达式如何大大简化了函数的逻辑（流程）。它确实更具可读性。另外，请注意您的原始功能是如何工作的，因为：

    一个。您的函数不会更新运行总计（结果）

    湾。即使确实如此，最终您最终还是会添加None一些内容，因为您的原始函数在素数 >= 2000000 的情况下没有返回任何内容。

于 2012-09-19T20:42:37.303 回答
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 回答
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 回答
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 回答