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

解题思路:
方法大佬们都讲了，线性筛。做实验测了一下效率，用纯数组写法比用vector快50ms左右，但是用纯数组有一点点坑，最后求和的终止条件要把数组大小纳入考虑，用vector的迭代器就没这个顾虑了。看了之前大佬们写的题解，好像有的没注意到这个问题，本地用VS测会翻车

注意事项:

参考代码:

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <fstream>

using namespace std;

#define N 5000000

long long primeCheck[N];
vector<long long> primeList;

//线性筛素数，合数都可以由两个素数或一个素数一个合数的乘积表示
void getPrime(long long n)
{
	for (long long i = 2; i <= n; i++)
	{
		//如果是之前就被标记的数，说明是素数，那么直接放入素数集合
		if (primeCheck[i] == 0)
			primeList.push_back(i);
		//筛去后面所有由素数和当前数的乘积构成的数，注意这里终止条件应当加上等号，否则n可能不会被筛掉
		for (long long j = 0; j < primeList.size() && i*primeList[j] <= n; j++)
		{
			primeCheck[i*primeList[j]] = 1;
			//不重复筛去，减小开销
			if (i%primeList[j] == 0)
				break;
		}
	}
}

long long getPrimeSum(int n)
{
	long long sum = 0;
	for (vector<long long>::iterator it = primeList.begin(); it < primeList.end(); it++)
	{
		if (*it <= n)
			sum += *it;
		else
			break;
	}
	return sum;
}

int main(void)
{
	long long n = 0;
	cin >> n;
	getPrime(n);
	cout << getPrimeSum(n) << endl;
	return 0;
}

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <fstream>

using namespace std;

#define N 5000000

long long primeCheck[N];
long long primeList[N];

//线性筛素数，合数都可以由两个素数或一个素数一个合数的乘积表示
int getPrime(long long n)
{
	int pos = 0;
	for (long long i = 2; i <= n; i++)
	{
		//如果是之前就被标记的数，说明是素数，那么直接放入素数集合
		if (primeCheck[i] == 0)
			primeList[pos++] = i;
		//筛去后面所有由素数和当前数的乘积构成的数，注意这里终止条件应当加上等号，否则n可能不会被筛掉
		for (long long j = 0; j < pos && (long long)i*primeList[j] <= n; j++)
		{
			primeCheck[i*primeList[j]] = 1;
			//不重复筛去，减小开销
			if (i%primeList[j] == 0)
				break;
		}
	}
	return pos;//返回素数列表集合的大小
}

//这里有一点小坑
long long getPrimeSum(int n, int size)
{
	long long sum = 0;
	int i = 0;
	while (primeList[i] <= n && i < size)
	{
		sum += primeList[i];
		i += 1;
	}
	return sum;
}

int main(void)
{
	long long n = 0;
	cin >> n;
	int primeListSize = getPrime(n);
	cout << getPrimeSum(n, primeListSize) << endl;
	return 0;
}