1099 性感素数 (20 分)

本文主要是介绍1099 性感素数 (20 分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

步骤

1. 判断N本身是不是性感素数
   a. N和N-6
   b. N+6和N
2. 从N+1枚举，判断这个数是不是性感素数
   a. 判断两种情况
   ⅰ. N-6
   ⅱ. N+6
   b. 判断一种情况
   ⅰ. N+6，（N+1和N+7）漏了N+1~N+5比N小的时候的匹配情况。
   ⅱ. 预先将N到N+5之间这几个数处理掉
3. 判断素数：
   a. 优化到根号n

代码

• 直接讨论两种情况

#include <iostream>
#include <cmath>
using namespace std;inline bool isPrime(int n){if(n <= 1) return false;int sq = sqrt(n);for(int i = 2; i <= sq; i++){if(n % i == 0) return false;}return true;
}
int main(){int N; cin >> N;auto a = isPrime(N);auto b = isPrime(N-6);auto c = isPrime(N+6);if(a && b){cout<<"Yes"<<endl;cout<<N-6<<endl;return 0;}if(a && c){cout<<"Yes"<<endl;cout<<N+6<<endl;return 0;}//本身不是cout<<"No"<<endl;for(int i = N+1; 1; i++){auto a = isPrime(i);if(!a) continue;auto b = isPrime(i-6);auto c = isPrime(i+6);if(a && (b || c)){cout<<i<<endl;return 0;}} return 0;
}

• 只讨论一种情况

#include <iostream>
#include <algorithm>
#include <cmath>
#include <unordered_map>
using namespace std;
unordered_map<int, bool> mp;
inline bool isPrime(int x){if(x <= 1) return false;int sq = sqrt(x);for(int i = 2; i <= sq; i++){if(x%i == 0) return false;}return true;
}int main() {int N;cin >> N;auto a = isPrime(N-6);auto b = isPrime(N);auto c = isPrime(N+6);if(a && b){cout<<"Yes"<<endl;cout<<N-6<<endl;return 0;}else if(b && c){cout<<"Yes"<<endl;cout<<N+6<<endl;return 0;}cout<<"No"<<endl;for(int i = N+1; 1; i++){auto v = isPrime(i);if(!v) continue;auto u = isPrime(i-6);if(u){if(i-6 < N) cout<<i<<endl;return 0;}}return 0;
} 

这篇关于1099 性感素数 (20 分)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---