写个裸的筛选法再加上位运算优化也就几秒就能算出来的
#include <stdio.h>
#include <math.h>
#define N 100000000
unsigned int a[(N>>5)+1];
int main() {
unsigned int i, j, k;
a[0] = 3;
for (i=2; i<=sqrt(N); i++)
if (!(a[i >> 5] & (1 << (i & 31)))) {
j = i << 1;
while (j <= N) {
a[j >> 5] |= (1 << (j & 31));
j += i;
}
}
j = 0;
for (i=0; i<=(N>>5); i++) {
k = a[i];
k = (k & 0x55555555) + ((k >> 1) & 0x55555555);
k = (k & 0x33333333) + ((k >> 2) & 0x33333333);
k = (k & 0x0F0F0F0F) + ((k >> 4) & 0x0F0F0F0F);
k = (k & 0x00FF00FF) + ((k >> 8) & 0x00FF00FF);
k = (k & 0x0000FFFF) + ((k >> 16) & 0x0000FFFF);
j += 32-k;
}
j -= 31-(N & 31);
printf("%d\n", j);
}