PAT basic 乙级

1099 性感素数

“性感素数”是指形如 (p, p+6) 这样的一对素数。

输入：一个正整数 N (≤$10^8$)
输出：如果存在 N-6 或 N+6 是素数，打印 Yes\nmin(N-6,N+6)；如果不存在，打印No，和大于N的最小的性感素数

Time Limit exceeded，应该是判断素数那里需要优化

#include
#include
using namespace std;
unordered_set<int> dp={2,3,5,7,11};
bool checkprime(int n){
    if(n<2) return false;
    if(dp.find(n)!=dp.end())return true;
    for(auto e:dp) // 任何数可以表示为素数的幂的乘积
        if(n%e==0)return false;
    
    for(int i=13; i<=n/2; i+=2)
        if(n%i==0)return false;
    dp.insert(n);
    return true;
}
void checksex(int n){
    if(checkprime(n)){
        if(checkprime(n-6)){cout<<"Yes"<<endl<<n-6;return;}
        if(checkprime(n+6)){cout<<"Yes"<<endl<<n+6;return;}
    }
    int i=n+1;
    for(; !(checkprime(i) && (checkprime(i-6) || checkprime(i+6)));
        i++);
    
    cout<<"No"<<endl<<i;
}
int main(){
    int n;cin>>n;
    checksex(n);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30