题解 P2640 【神秘磁石】
引领天下
2017-08-31 16:25:27
来发一个比楼下们快的方法。
本题我用的是筛法，但是我优化了！
具体优化的方法呢，就是楼下们太暴力了，竟然直接暴力！（从 $1$ 到 $n$）
然而我们有更快的方法！
在筛法打质数表的时候，我不仅保留了 bool 数组（用来判断），还开了一个整数数组，存下了质数，这样，我们就直接用质数表暴力。
这样，就可以直接循环质数，提高了效率。
上代码：
```cpp
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <iomanip>
using namespace std;
int n,k,a[3000],ps;//n，k为题目中的变量，a数组为质数数组，ps为质数下标
bool s[10005]={1,1},ok=1;//s数组为桶，ok为判断有没有满足条件的质数对的变量
void $(){
for (int i=2;i<10001;i++)//筛法标准做法
if (!s[i]){//s[i]=1表示不为质数，=0则是
a[ps++]=i;//把i这个质数存下来
for (int j=i*2;j<10001;j+=i)s[j]=1;//循环标记
}
}
int main(){
$();//预处理
scanf ("%d%d",&n,&k);
for (int i=0;a[i]<=n&&a[i]+k<=n;i++)if (!s[a[i]+k])//暴力，符合条件就输出
ok=!printf ("%d %d\n",a[i],a[i]+k);
if (ok)printf ("empty");//没有就输出empty
//不要被题目中“相差为k的质数对”所迷惑，实际上，如果你多判一次a[i]-k，答案会输出两遍。具体为什么，自己想。
return 0;
}
```