罗恩祥 • 2个月前
思路分析 首先,2是一个灰常特殊的质数,唯一的偶质数 2是费马二平方质数吗,显然不是 所以任意一个费马二平方质数都为奇数 故每一个费马二平方质数都可表达为 4 + (k + 1) * (k + 1) 所以,我们可以先枚举sqrt(N)以内最大的质数(倒序枚举),记为maxx 接着枚举k,范围3 ~ maxx
如果k*k + 4为质数
输出它
代码附上!
#include <bits/stdc++.h>
using namespace std;
bool prime(int n) //质数判断部分
{
if(n == 1)
return 0;
if(n == 2)
return 1;
for(int i = 2;i <= sqrt(n);i++)
if(n % i == 0)
return 0;
return 1;
}
int N;
int maxx = 0;
int main()
{
cin >> N;
for(int k = sqrt(N);k >= 2;k--) //因为k的平方不能超过N,故从 sqrt(N) 开始倒序枚举,降低时间复杂度
{
if(prime(k))
{
maxx = k;
break;
}
}
for(int k = 3;k <= maxx && 2 * 2 + k * k <= N;k++) //枚举k
{
if(!prime(k)) //优化
continue;
if(prime(2 * 2 + k * k))
printf("%d\n",2 * 2 + k * k);
}
}
~~看到最后了,浅浅的求个赞吧,恳请各位巨佬高抬贵手,给蒟蒻点个赞吧qwq
评论: