题目10：计算两百万以下所有质数的和

欧拉计划 · 发表于 2023-5-29 18:11:12

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由欧拉计划于 2023-7-8 05:11 编辑

题目10：计算两百万以下所有质数的和

Summation of primes

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

题目翻译：

10 以下所有质数的和是 2 + 3 + 5 + 7 = 17。

请找出两百万以下所有质数的和。

视频讲解：

思路解析及源码参考（C & Python）：

游客，如果您要查看本帖隐藏内容请回复

鱼C-小师妹 · 发表于 2023-5-29 19:27:58

zhangjinxuan · 发表于 2023-5-29 19:28:28

#include <bits/stdc++.h>
using namespace std;

int c[1000001], tot;
bool is[3000001];
long long sum = 0;

int main() {
    for (int i = 2; i <= 2000000; ++i) {
        if (!is[i]) c[++tot] = i, sum += i;
        for (int j = 1; j <= tot && c[j] * i <= 2000000; ++j) {
            is[c[j] * i] = 1;
            if (i % c[j] == 0) break;
        }
    }
    printf("%lld\n", sum);
    return 0;
}

万能的欧拉筛

时间复杂度刚好适合

欧拉计划 · 发表于 2023-5-29 20:17:15

zhangjinxuan 发表于 2023-5-29 19:28
万能的欧拉筛

时间复杂度刚好适合

发明欧拉筛的人简直是一个天才！

歌者文明清理员 · 发表于 2023-5-29 20:19:12

小甲鱼的二师兄 · 发表于 2023-5-29 21:43:20

欧拉计划发表于 2023-5-29 20:17
发明欧拉筛的人简直是一个天才！

确实厉害

auend · 发表于 2023-6-2 14:12:14

好像有点难

白于玉 · 发表于 2023-6-6 00:27:44

本帖最后由白于玉于 2023-6-6 00:34 编辑

def PrimeNumberJudgement(n):
    if n in [2,3]:
        return 1
    elif n % 2 == 0:
        return 0
    elif n % 6 not in [1,5]:
        return 0
    else:
        for i in range(3,int(n**0.5)+1,2):
            if n % i == 0:
                return 0
        return 1

s = 2
for i in range(3,2000000,2):
    if PrimeNumberJudgement(i):
        s += i
print(s) # 输出142913828922

PH.Chen · 发表于 2023-6-12 10:02:14

学习一下

vemonz · 发表于 2023-6-16 09:44:00

小草帽 · 发表于 2023-6-25 11:14:56

想看下答案

高山 · 发表于 2023-6-28 06:19:39

支持

冰河入梦 · 发表于 2023-7-8 11:00:35

？

傲然子 · 发表于 2023-7-8 15:00:25

让我康康！

gurite · 发表于 2023-7-8 19:27:14

pixie99 · 发表于 2023-7-11 09:33:50

Mr.roushan · 发表于 2023-7-19 09:16:55

看下结果

水船船船 · 发表于 2023-7-21 10:56:00

kangzhenrong · 发表于 2023-7-23 19:58:54

想看看答案

小坛砸 · 发表于 2023-7-24 11:50:57

拿来吧你

账号		自动登录	找回密码
密码			立即注册

题目10：计算两百万以下所有质数的和

马上注册，结交更多好友，享用更多功能^_^

评分