python 素数算法

Question

假设函数 is_prime 可用。假设变量n已与正整数相关联。编写所需的语句，找出在超过 n 之前可以添加多少个素数(从 2 开始，按递增顺序依次增加素数 [2,3,5,7,11,13,...])。将此数字与变量 k 相关联。

 def main():
    n=int(input('n: '))
    k=0
    i=2
    sum=0

    while sum<=n:
        if is_prime(i):
            sum+=i
            i+=1
            k+=1
        print(k)



def is_prime(n):

    for divisor in range(2,int(n**0.5)+1):
        if n/divisor==int(n/divisor):
            return False
    return True

main()

非常感谢一些指点。

我稍微修改了代码，它工作正常，但是对这些代码进行评分的程序说我几乎肯定应该在某些地方使用+号。我不知道。修改后的代码为:

while sum<=n:

        if is_prime(i):

            sum+=i
            k+=1
            i+=1
    print(k)

输出:

n:10

我:2

2

我:3

5

当它实际上应该达到 i=5 且总计 =10 时。

Answer 1

其实有一个更高效的解决这个问题的方法，那就是埃拉托斯特尼筛法。基本思想是生成从 2 到 n 的数字数组。然后从 2 开始迭代这个数组，并用 -1 替换所有数字，其中 mod by i == 0 或删除它们。

如果您遇到困难，可以在此处检查实现情况。

Sieve of Eratosthenes - Finding Primes Python