0

假设一个函数的可用性is_prime。假设变量 n 与一个正整数相关联。写出计算前 n 个素数之和所需的语句。总和应与变量总计相关联。

注意: is_prime将整数作为参数,True当且仅当该整数是素数时才返回。好吧,我写了is_prime这样的函数:

def is_prime(n):
    n = abs(n)
    i = 2
    while i < n:
        if n % i == 0:
            return False
        i += 1
    return True

但它的工作原理除了 n=​​=0。如何修复它以使其适用于每个整数?我正在尝试找出如何编写函数来获取前 n 个素数之和以及如何修改我的 is_prime 函数的答案,该函数应该适用于所有可能的输入,而不仅仅是正数。

4

5 回答 5

5

你的任务如下。

假设函数 is_prime 的可用性。假设变量 n 与一个正整数相关联。写出计算前 n 个素数之和所需的语句。总和应与变量总计相关联。

正如 NVRAM 在评论中正确指出的那样(似乎没有其他人注意到),问题是“假设功能的可用性is_prime”。

您不必编写该函数要做的是“编写计算前 n 个素数之和所需的语句”。

其伪代码类似于:

primes_left = n
curr_num = 2
curr_sum = 0
while primes_left > 0:
    if is_prime(curr_num):
        curr_sum = curr_sum + curr_num
        primes_left = primes_left - 1
    curr_num = curr_num + 1
print "Sum of first " + n + " primes is " + curr_sum

我想你会发现,如果你只是用你选择的语言来实现那个伪代码,那么你所要做的就是一切。

如果您正在寻找一个实现is_prime来测试您的分配,那么它的效率并不重要,因为无论如何您只会测试一些小值。考虑到将要使用它的代码的限制,您也不必担心小于 2 的数字。这样的事情是完全可以接受的:

def is_prime(num):
    if num < 2:
        return false
    if num == 2:
        return true
    divisor = 2
    while divisor * divisor <= num:
        if num % divisor == 0:
            return false
        divisor = divisor + 1
    return true
于 2009-11-23T09:29:02.053 回答
2

在您的问题陈述中,它说 n 是一个正整数。因此assert(n>0)并确保您的程序外循环永远不会is_prime()带有负值或零。

您的算法 - 每个连续奇数的试验除法(“奇数”对您来说是一个主要的加速) - 有效,但会非常慢。查看初筛以获取灵感。

于 2009-11-23T06:10:42.667 回答
0

为什么不直接硬编码 i = 0 或 1 的答案?

n = abs(n)
i = 2
if(n == 0 || n == 1)
   return true //Or whatever you feel 0 or 1 should return.
while i < n:
    if n % i == 0:
        return False
    i += 1
return True

您可以通过省略一些数字来进一步提高算法的速度。此脚本仅检查 n 的平方根,因为如果一个数字有一个或多个因数,则没有一个合数的因数大于其平方根,将在该数的平方根之前遇到一个。在测试大量数字时,这会产生很大的不同。

n = abs(n)
i = 2
if(n == 0 || n == 1)
   return true //Or whatever you feel 0 or 1 should return.
while i <= sqrt(n):
    if n % i == 0:
        return False
    i += 1
return True
于 2009-11-23T06:07:10.387 回答
0

那么,当 n 为 0 或 1 时会发生什么?

你有

i = 2
while i < n: #is 2 less than 0 (or 1?)
     ...
return True

如果您希望 n of 0 或 1 返回False,那么这是否表明您需要修改条件(或函数本身)以解决这些情况?

于 2009-11-23T06:10:42.423 回答
-1

尝试这个:

 if(n==0)
    return true
 else
    n = abs(n)
    i = 2
    while i < n:
        if n % i == 0:
            return False
        i += 1
    return True
于 2009-11-23T06:11:11.247 回答