【题目描述】费马二平方质数(sprime)
除2这个特别的质数外,其它质数都可以分成两类:第一类是被4除余1的质数,如5,13,17,29,37,41;第二类是被4除余3的质数,如3,7,11,19,23,31。奇怪的是:第一类质数都能转成两个整数的平方和,第二类则不能。如: 5=1×1+2×2 13=2×2+3×3 17=1×1+4×4 29=2×2+5×5 这就是费马二平方定理。上述有的等式右侧的数恰好是两个质数,如上面的13和29两个数的等号右侧就都是质数,我们将此类质数取名为“费马二平方质数”。试编程打印N以内的所有费马二平方质数(N≤2×10^9)。
输入
输入一个整数N。
输出
输出N以内的所有费马二平方质数。
样例
输入
50
输出
13
29
#include<bits/stdc++.h>
using namespace std;
bool prime(int x){
if(x%2==0) return false;
for(int i=3;i*i<=x;i+=2){
if(x%i==0) return false;
}
return true;
}
int main(){
int n;
cin >> n;
cout << 13 << endl << 29 << endl;
for(int i=53;i<=n;i+=10){
if(prime(i)){
if(int(sqrt(i-4))==sqrt(i-4)&&prime(sqrt(i-4))){
cout << i << endl;
}
}
}
return 0;
}