编码挑战：求一千万自然数中质数和

[SlipStupig]

语言只能用 python ，求一千万自然数总质数总和，速度最快的有奖励哦

可能我没说清楚规则，一千万不是 0-1000 万，而是自然数范围内任意一千万个数字，提交代码请注意提交一下你运行的 profile （最少也要有个运行总时间吧），测试标准环境是 i7 4700MQ 4core 4gb 内存 ddr3 1600

[ilcwd23]

打表？

[whisperzzzz]

3203324994356

[auser]

速度最快的难道不是直接打印结果？
不知道哪本书有写过哪个美国大学举办了类似比赛，然后……第一名开销是负数。

[mickeyandkaka]

https://en.wikipedia.org/wiki/Prime-counting_function#Algorithms_for_evaluating_.CF.80.28x.29
上面稍微改造下，可以使得复杂度到 sqrt(n)

[congeec]

http://www.zhihu.com/question/29580448

[knightdf]

那 CPU 多的赢了，判断 2-sqrt(n)就行了

[congeec]

@auser 卡内基梅隆大学编程难题

[ianluo]

@ilcwd23 神马意思？

[random2case]

private static final int MAX = 100000000;
private static final int ARRAY_SIZE = (int) Math.round((MAX * 1.1) / Math.log(MAX));
private static int[] array = new int[ARRAY_SIZE];
//--//
int pos = 0;
array[pos++] = 2;

int sqrtN = 3;
int countSqrtN = 2;

for (int i = 3; i < MAX; i += 2) {
for (int j = 0; j < pos; j++) {
int value = array[j];
if (value > sqrtN) {
premier = true;
break;
}
if ((i % value) == 0) {
premier = false;
break;
}
}

if (premier) {
array[pos++] = i;
}

if (--countSqrtN == 0) {
countSqrtN = sqrtN;
sqrtN++;
}
}


给一个 java 版的吧，暂时找不到当时 python 写的了，自己改编一下吧

[whisperzzzz]

@congeec 几个月前看这个 DP 觉得简直丧心病狂……

[whisperzzzz]

@knightdf 判断单个的话可以 Miller-Rabin ，多取几个数就好了……

[XiaoxiaoPu]

#include <stdio.h>
#include <string.h>
#include <stdlib.h>


static inline int getbit(int *bits, int i)
{
return (bits[i>>5] >> (i & 31)) & 1;
}

static inline void setbit(int *bits, int i)
{
bits[i>>5] |= (1 << (i & 31));
}

static inline void clrbit(int *bits, int i)
{
bits[i>>5] &= ~(1 << (i & 31));
}

int isqrt(int num)
{
register int x1 = num, x2;

do
{
x2 = x1;
x1 = (x1 + num / x1) / 2;
} while (x1 < x2);
return x2;
}


int main()
{
int n = 10000000;
int *bits;

bits = (int *)malloc(((n>>5)+1) * sizeof(int));
if (bits == NULL)
{
fprintf(stderr, "Out of memory.\n");
return 1;
}

for (int i = 0; i < ((n>>5)+1); i++)
{
bits[i] = ~0;
}

clrbit(bits, 0);
clrbit(bits, 1);
clrbit(bits, 4);

int end = isqrt(n);
long sum = 0;
for (int i = 2; i <= end; i++)
{
if (getbit(bits, i))
{
sum += i;
int j0 = n / i;
for (int j = 2; j <= j0; j++)
{
clrbit(bits, i * j);
}
}
}

printf("%ld\n", sum);

return 0;
}



发个 C 写的
➜ ~ gcc -o prime -std=gnu99 -O3 prime.c
➜ ~ time ./prime
642869
./prime 0.04s user 0.00s system 94% cpu 0.046 total
➜ ~

[XiaoxiaoPu]

啊哦，上面发的错了，这个才对

#include <stdio.h>
#include <string.h>
#include <stdlib.h>


static inline int getbit(int *bits, int i)
{
return (bits[i>>5] >> (i & 31)) & 1;
}

static inline void setbit(int *bits, int i)
{
bits[i>>5] |= (1 << (i & 31));
}

static inline void clrbit(int *bits, int i)
{
bits[i>>5] &= ~(1 << (i & 31));
}

int isqrt(int num)
{
register int x1 = num, x2;

do
{
x2 = x1;
x1 = (x1 + num / x1) / 2;
} while (x1 < x2);
return x2;
}


int main()
{
int n = 10000000;
int *bits;

bits = (int *)malloc(((n>>5)+1) * sizeof(int));
if (bits == NULL)
{
fprintf(stderr, "Out of memory.\n");
return 1;
}

for (int i = 0; i < ((n>>5)+1); i++)
{
bits[i] = ~0;
}

clrbit(bits, 0);
clrbit(bits, 1);
clrbit(bits, 4);

int end = isqrt(n);
for (int i = 2; i <= end; i++)
{
if (getbit(bits, i))
{
int j0 = n / i;
for (int j = 2; j <= j0; j++)
{
clrbit(bits, i * j);
}
}
}

long sum = 0;
for (int i = 2; i <= n; i++)
{
if (getbit(bits, i))
{
sum += i;
}
}
printf("%ld\n", sum);

return 0;
}


➜ ~ gcc -o prime -std=gnu99 -O3 prime.c
➜ ~ ./prime
3203324994356
➜ ~

[msg7086]

好没挑战啊。某节大二课后作业就是用 pthread 做并行筛法求质数， INTMAX 之内的所有质数，最后求总数。这个改成求和也并不难，把统计时候的 cnt++ 改成 sum+=x 就行了。

[msg7086]

另外这题目也太不规范了。比如「自然数范围内任意一千万个数字」，自然数范围大了，难道要支持几万位的数字？

[sinxccc]

@auser "Expert C Programming: Deep C Secrets" 里的段子。

[SlipStupig]

@msg7086 大整数加减有何不可，你代码够优秀放出来

[em70]

任意 1000 万个数字，不一定是连续的数字吧，不一定没有重复吧，也就是说是包含 1000 万个无规律数字的数组中求质数总和?

[SlipStupig]

@em70 很正确

[knightdf]

@whisperzzzz 这个好像是更专业

[linux40]

。。。这个问题难道不是在常数时间么。。。

[mulog]

太不严谨了吧 连个范围都没有。
「任意自然数中质数和」？你能把所有自然数中的质数都找出来吗？
目前已知最大质数是 2^74207281 ，有那个本事先找出个更大的上上新闻联播再说。。

[odirus]

我觉得如果要比赛，至少你要先确定范围撒，还要有相同的运行环境撒。。。我去哪里找 "i7 4700MQ 4core 4gb 内存 ddr3 1600" 这种环境？

[slixurd]

https://leetcode.com/problems/count-primes/
你们可以试试在 leetcode 上做下，虽然题目不完全一样。
如果你的答案能比 90%以上的人快，才说明你做得好，如果用它 hint 的方法或者暴力求解，速度不会快的。

[Hello1995]

@mulog 2^74207281 显然不是素数。

[mulog]

@Hello1995
哈哈哈哈 对
2^74207281 - 1

[JayXon]

@slixurd 那个题 test case 太简单，根本比不出什么，我的代码跑出来是 0 ms

[slixurd]

@JayXon 啊对，那的 testcase 太弱
话说你该不会是做 Thunder JayXon 版的那个 JayXon 吧

[msg7086]

@SlipStupig 题目都没出明白还要人做么。
别说乱取一千万个数，我就取这一千万个数的个位和十位，连在一起组成一个两千万位的数，你要跑多久？
已知 22 楼那个大数有 2234 万位，拿 i7 不间断跑了 31 天。
来吧，不管你代码优秀不优秀，都可以放出来，我们来看看半年能不能跑完？

[Xs0ul]

@mulog 你说的那是最大的梅森素数，并不是最大的素数

[mulog]

@Xs0ul
咦 google 出来几个源都说是这个数 那请问现在已知最大的素数是多少？

[Xs0ul]

@mulog 我建议你搜下“梅森素数”

[brbrarts]

@Xs0ul 2^74207281-1 是最大的梅森素数，同时也是最大的已知素数

我觉得梅森素数另外还有一个优势，就是表达很简洁。 2^74207281-1 写出来有两千多万位，假设有一个更大的素数，并且他不能用这种简洁的方式表现出来，那你怎么告诉别人这个数是多少呢？在贴子里贴两千多万位数字么。。。

[JayXon]

@slixurd 是啊

[slixurd]

@JayXon 遇到大神了
记得三四年前基本上都是用你迅雷修改版的
直到后来上了 Linux.....