楼上的理解不对，就是1000000个素数。
第1000000个素数为15485863，前100000个素数的和是7472966967499。

关于这个问题，可以将查表法和素数筛选相结合，用一部分空间来换取时间。比如记录每1000个素数的和及相应素数，那么对于具体的N可以从离它最近的记录开始，最多做1000次素数查找就可以。计算前1000000个的和绝对超不过1秒。
本来想贴代码的，太长，这里放不下。

我承认我错了 你把代码压缩 给我吧  我想崇拜一下您!我没看仔细

9 楼没理解错，就是找 1,000,000 个质数，不过嘛，随便喷人的习惯很不好撒。
而且俺不是 SB。 找前 1,000,000 个质数非常容易，他找不到只说明他有够菜

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

#define max 15485864

char is_prime_p[max] = {0};
unsigned long long int nth_prime_sum[1000001] = {0};

int main(int argc, char *argv[]) {
    int i, j, l = 2;
    
    // Sieve to get primes and the sums.
    for (i = 3; i < max; i += 2) {
        is_prime_p[i] = 1;
    }
    nth_prime_sum[1] = 2;
    for (i = 3; i < max; i += 2) {
        if (is_prime_p[i]) {
            nth_prime_sum[l] = nth_prime_sum[l - 1] + i;
            l++;
            for (j = i * 3; j < max; j += i << 1) {
                is_prime_p[j] = 0;
            }
        }
    }
    
    // The following printf() is for mingw only. 
    // Please modify the format string according to 
    // your compiling environment.
    printf("Sum of first 1,000,000 primes is %I64u\n",
            nth_prime_sum[--l]);
    if (argc > 1 && strcmp(argv[1], "-q") == 0) {
        printf ("Give me an integer n, and I'll tell you the "
                "sum of first n primes.\n"
                "Intput any non-numeric character, a number bigger "
                "than 1,000,000 or a negative number to quit\n"
                "n: ");
    
        // Allows the user to do queries.
        while (scanf("%d", &l) == 1 && l <= 1000000 && l >= 0) {
            while (getchar() != '\n');
            printf ("   %I64u\n\n", nth_prime_sum[l]);
            printf("n: ");
        }
    }
    
    return 0;
}

运行程序的时候加参数 -q 可以自由查询前 n 个质数的和 (0 <= n <= 1,000,000)。
直接运行计算前 1,000,000 个质数的和。
mingw time 显示运行时间 641ms，内存 24MB 以下
gcc -O3 的话直接运行时间 600ms 以下

[ 本帖最后由 voidx 于 2011-8-21 14:36 编辑 ]

lz在做OJ的题目啊

筛法秒杀

预处理。。2的倍数全除掉，3的倍数全除掉。。。。依次上去

路过

福建农林大学OJ 1011就是这个题。我实在想不通这段代码为什么会是WA。

#include <stdio.h>
#define MAX_N      16000000
#define MAX_SUM    1000001
char prime[MAX_N];
long long sum[MAX_SUM];
int count = 0;
void test()
{
    int i, j;
    for(i = 2; i < MAX_N; i++)
    {
        if(prime[i]) continue;
        sum[count + 1] = sum[count] + i;
        count++;
        if(count >= MAX_SUM - 1) break;
        for(j = i << 1; j < MAX_N; j += i)
            prime[j] = 1;
    }
}
int main()
{
    int n;
    test();
    while(scanf("%d", &n) != EOF)
        printf("%lld\n", sum[n]);
    return 0;
}

 

我知道怎么回事了。

定义 long long int 要用 __int64，FAQ 里面说的。
printf() 输出 long long int 要用 %I64d，自己试出来的

蛋疼

[ 本帖最后由 voidx 于 2011-8-22 13:37 编辑 ]

收到的鲜花

• beyondyf 于 2011-08-22 15:42 送鲜花  5朵   附言：谢了
• beyondyf 于 2011-08-22 15:43 送鲜花  5朵   附言：再谢一次