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

[SlipStupig]

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

[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 这个好像是更专业