素数求和- 素数筛法

素数求和:

Description:

      The problem is very simple,your job is just to calculate the sum of primes from the first prime to the Nth prime.

Input:

The input consists multiple cases. Each line contains a N(1<=N<=1000000).

Output:

For each N,output the result of this problem that describe before.

Sample Input:

1

3

5

Sample Output:

2

10

28

知识介绍：

素数原理公式：

估计n以内有多少个质数   n/ln(n)

二次筛法原理：

https://en.wikipedia.org/wiki/Quadratic_sieve

#include <cstdio>
#include <string.h>
#include <math.h>
#include <cstdlib>
#include <iostream>
#include <time.h>


const long long MAXN =  60000000;
const long long MAXN2 = 60000000;
bool IsPrime[MAXN];
__int64 sum[MAXN2]={0};
__int64 i,j;


using namespace std;


void prime()
{
	int cnt = 2;
	sum[1] = 2;
	for(i=3;i<=MAXN;i+=2){//偶数一定不是素数 
		if(!IsPrime[i])
		{
			sum[cnt] = i + sum[cnt-1];
			cnt++;
			for(j=i*i;j<=MAXN;j+=i*2)
			{
				IsPrime[j] = true;
			}
		}
	}
}

int main()
{
	int n;
	while(scanf("%d",&n)!=EOF){
		printf("%I64d\n",sum[n]);
	}
    return 0;
}