回复 10楼 九转星河
有兴趣,又能赚钱是最好。
#include<stdio.h> #include<math.h> #include<time.h> #define TRIM(a) ((a)>r)?(a)=2*r - n/(a) + 1:(a)=(a); _int64 V[100000],S[100000]; // where V is the array of index, and S[i] denotes sum of primes less than i int main() { int start = clock(); _int64 n = 1000000000,r,k; //_int64在有的编译器里用long long替代 r = (int)sqrt((double)n); for(k = 0; k < r + 1; k++) { V[k] = k; S[k] = (k*(k+1))/2 - 1; } for(; k < 2*r + 1;k++) { V[k] = n/(2*r - k + 1); S[k] = (V[k]*(V[k]+1))/2 - 1; } for(_int64 p = 2; p < r + 1; p++) { if(S[p]>S[p-1]) { // this condition satifise only when p is prime _int64 sp = S[p-1],p2 = p*p; for(_int64 j = k-1; j > 1; j--) { if(V[j] < p2)break; _int64 a = V[j], b = a/p; TRIM(a); TRIM(b); // makes the indices correct S[a] -= p*(S[b] - sp); // sieve out the sum of composite numbers in S[a] which divided by p } } } printf("%I64d\n",S[2*r]); printf("Total time is: %lf s\n",(double)(clock() - start)/1000); return 0; }