1 条题解
-
0Guest LV 0
-
0
//这题看名字感觉挺牛逼的 实际上只是一道水题
//要求两个差值最大的质数 不需要想怎么筛素数 在一个一个找 很耗时
//想一下 是不是两个数一个尽量小 一个尽量大 那么他们的差值是不是就会最大?
//所以我们就只需要从小的先开始 用试除法 每找出一个素数i 就判断一下他的另外一边 n-i 是不是也//符合条件 放心时间空间上都不会爆 因为那个尽量小的值的确很小
#include<bits/stdc++.h>
using namespace std;
int n;
bool prime(int x)
{//试除法
for(int i=2;i<=sqrt(x);i++)
{
if(x%i==0) return false;
}
return true;
}
int main()
{
while(cin>>n&&n!=0)
{
for(int i=2;i<=n/2;i++)
{//这里注意一下 我一开始写了一个 i乘以i<=n 的优化 结果反而爆了
//因为要从两头开始找数字 那是不是像分治的思想一样 找到中间的数为止
//如果像我那样写的话就变成了只找到了√n 当数据大的话 √n就会比中间的那个数还小(聪明反被聪明误)
if(prime(i)&&prime(n-i))
{
cout<<n<<" = "<<i<<" + "<<n-i<<endl;
break;
}
}
}
return 0;
}
//来自某届石光中学信竞苟蒻学长 愿看到此文的你 努力码题 为校争光
- 1