蓝桥杯算法提高VIP-素数求和 （C语言代码）

解题思路:
经计算，当输入n为2000000时，小于等于n的素数之和为142913828922，有12位，这明显大于无符号整型所能表示的最大数4294967295，所以保存和的变量或数组的数据类型只好定义为unsigned long long，计算得到最大数为：18446744073709551615，它的最大数约有20位，若求和需要查表，除了素数查表所用的8M内存，还需要另外开辟16M内存做为求和表空间。

注意事项:
若测试用例有很多组，为了防止每次重新求和有可能超时，可以事先用数组保存逐步求和的中间结果。

参考代码:

#include<stdio.h>
#include<math.h>
#define N 2000000
int p[N+1]={0};
unsigned long long S[N+1];
int main(){
    int i,j,T,n;
    unsigned long long s;
    p[0]=p[1]=1;
    T=floor(sqrt(N)+0.5);
    for(i=2;i<=T;i++){
        if(!p[i]){
            for(j=i*i;j<=N;j+=i)
                p[j]=1;//标记合数
        }
    }
    s=0;
    for(i=0;i<=N;i++){
        if(!p[i]) s+=i;//加“非合数”
        S[i]=s;//小于等于i的素数之和
    }
    while(~scanf("%d",&n))
        printf("%llu\n",S[n]);//查求和表
    return 0;
}