F - Goldbach`s Conjecture kuangbin 基础数论

<cstdio> #include<cmath> #include<cstring> #include<sstream> #include<algorithm> #include<queue> #include<deque> #include<iomanip> #include<vector> #include<cmath> #include<map> #include<stack> #include<set> #include<fstream> #include<memory> #include<list> #include<string> using namespace std; typedef long long LL; typedef unsigned long long ULL; #define MAXN 10000001 #define L 31 #define INF 1000000009 #define eps 0.00000001 /* 打表 把所有素数存到一个vector中 然后用一个map保存所有和出现的次数 然后直接找就可以 */ bool notprime[MAXN]; vector<int> prime; void Init() { memset(notprime, false, sizeof(notprime)); notprime[1] = true; for (int i = 2; i < MAXN; i++) { if (!notprime[i]) { prime.push_back(i); for (int j = i + i; j < MAXN; j += i) notprime[j] = true; } } } int main() { Init(); int T,n; cin >> T; for(int cas=1;cas<=T;cas++) { cin >> n; vector<int>::iterator p = lower_bound(prime.begin(), prime.end(), n/2); //cout << *p << endl; int cnt = 0; for (vector<int>::iterator it = prime.begin(); it <= p && *it<=n/2; it++) { if (!notprime[n - *it]) { //cout << *it << ‘ ‘ << n - *it << endl; cnt++; } } printf("Case %d: %d\n", cas, cnt); } return 0; }

 

F - Goldbach`s Conjecture kuangbin 基础数论

标签：0.00   problems   iterator   tar   integer   map   wan   cas   iostream