求给定正整数m以内的素数之和
时间: 2023-12-22 17:04:11 浏览: 102
kata-primeNumbers:只是一些练习
这可以通过筛法求解,具体来说,可以使用埃氏筛法或欧拉筛法,这里我给出欧拉筛法的实现代码:
```python
def prime_sum(m):
prime = [True] * (m + 1)
primes = []
for i in range(2, m + 1):
if prime[i]:
primes.append(i)
for j in range(len(primes)):
if i * primes[j] > m:
break
prime[i * primes[j]] = False
if i % primes[j] == 0:
break
return sum(primes)
print(prime_sum(10)) # 输出结果为 17,即 2 + 3 + 5 + 7 = 17
```
其中,`prime[i]` 表示 i 是否为素数,初始时都为 True。然后使用 `primes` 列表来保存已经筛选出来的素数,然后对于每个素数 p,遍历从 p 开始的 p 的倍数,将其标记为非素数,并且如果当前的数 i 能够整除 p,就停止遍历,因为这样能够保证每个合数只会被它的最小质因数筛选一次。最后,将 `primes` 列表中的素数进行求和,即可得到正整数 m 以内的素数之和。
阅读全文