504006 - 费马二平方质数

【题目描述】费马二平方质数(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
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题