2-N之间的孪生素数的个数

额，判断一个数是否是素数：

bool isPrime(int n){ for(int i = 3; i * i <= n; i += 2){//偶数不用考虑 if(n%i == 0) return false; } return true; }

既然要相隔为2，那么枚举就可以了：

#include <iostream> #include <vector> using namespace std; int sign[10010];//记忆化 void isPrime(int n){ for (int i = 3; i * i <= n; i += 2){ //偶数不用考虑 if (n % i == 0) return; } sign[n] = 1; } int main(){ int n; cin >> n; for(int i = 3; i <= n; i += 2) isPrime(i); int res = 0; for(int i = 5; i <= n; i += 2){ if(sign[i] == 1 && sign[i-2] == 1) ++res; } cout << res << endl; return 0; }

优化一下，思路和这儿的最后一种方法类似： LeetCode第 204 题：计数质数(C++)_zj-博客

#include <iostream> using namespace std; int sign[10010];//记忆化 int main(){ int n; cin >> n; for(int i = 2; i <= n; ++i){ if(sign[i] == 0){ for(int j = i+i; j <= n; j += i) sign[j] = 1; } } //for(int i = 0; i <= n; ++i) cout << sign[i] << " "; //cout << endl; int res = 0; for(int i = 5; i <= n; i += 2){ if(sign[i] == 0 && sign[i-2] == 0) ++res; } cout << res << endl; return 0; }