F - Goldbach`s Conjecture（埃氏筛法 及 欧拉筛(线性筛))解题

 

 

 

 

---

 

 

AC代码如下

#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int maxn = (int)1e7;
//这里挺坑的，需要开 maxn / 10 的数组才行，开maxn的话会Runtime Error  
int prime[maxn / 10]; //存储素数(从下标1开始，并且素数大小是升序的)
bool isprime[maxn + 1];
//欧拉筛
void Prime() {
	memset(isprime, 1, sizeof(isprime)); //一开始把全部数初始化为素数，后面把不是素数的数筛选掉
	isprime[0] = 0; //0不是素数
	isprime[1] = 0; //1不是素数
	for (int i = 2; i <= maxn; i++) {
		if (isprime[i]) {
			prime[++prime[0]] = i; //记录素数，prime[0]相当于cnt，用来记录素数的个数
		}
		for (int j = 1; j <= prime[0] && i * prime[j] <= maxn; j++) {
			ll temp = (ll)i * prime[j];
			isprime[temp] = 0;
			if (i % prime[j] == 0) { //跳出循环
				break;
			}
		}
	}
}

//埃氏筛法 
/*void Prime() {
	memset(isprime, 1, sizeof(isprime)); //一开始把全部数初始化为素数，后面把不是素数的数筛选掉
	isprime[0] = isprime[1] = 0; //0和1不是素数
	for (int i = 2; i <= maxn; i++) {
		if (isprime[i]) { //如果i是素数，让i的所有倍数都不是素数
			prime[++prime[0]] = i;
			for (ll j = (ll)i * i; j <= maxn; j += i) {
				isprime[j] = 0;
			}
		}
	}
}*/

int main()
{
	Prime();
	int cnt = prime[0]; //cnt为素数的个数 
	int t;
	cin >> t;
	for (int l = 1; l <= t; l++) {
		int n;
		cin >> n;
		int ans = 0;
		for (int i = 1; i <= cnt; i++) {
			//if (prime[i] * 2 > n) break; //等价于下面语句 
			if (n - prime[i] < prime[i]) break; //当a>b时，不符合条件 
			if (isprime[n - prime[i]]) {
				ans++;
			}
		}
		cout << "Case " << l << ": " << ans << endl;
	}

	return 0;
}