A30630.素数对 题解

这里使用的是筛法

把 $2$ ~ $\sqrt n$ 的所有(质)数的非本身的倍数标记为非质数

#include <bits/stdc++.h>
using namespace std;
int n;
bool a[10005];
int main(){
    cin>>n;
    for (int i=2;i*i<=n;i++){
        for (int j=i*2;j<=n;j+=i){
            a[j]=true;
        }
    }
    int i=3;
    while (i<=n-2){
        if (!a[i]&&!a[i+2]){
            cout<<i<<' '<<i+2<<endl;
        }
        i+=2;
    }
    return 0;
}