问题1854--桐桐的发现(work)

1854: 桐桐的发现(work)

时间限制: 1 Sec  内存限制: 128 MB
提交: 10  解决: 2
[提交] [状态] [讨论版] [命题人:]

题目描述

桐桐发现一个有趣的现象:除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两个数所在式子的等号右侧就是素数,桐桐把这样的素数取名为“奇妙素数”。即:如果一个素数F能够表示成两个素数的平方和形式F=X×X+Y×Y,其中X,Y都是素数,那么它就是奇妙素数。
请你帮助桐桐把所有不大于N的奇妙素数打印出来。

输入

只有一个整数N(3≤N≤108)。

输出

第1到N行:输出不大于N的所有奇妙素数。每行输出一个,并把平方和的形式输出:F=X×X+Y×Y;
第N+1行:输出不大于N的所有奇妙素数的总数。

样例输入 Copy

30

样例输出 Copy

13=2*2+3*3
29=2*2+5*5
2

来源/分类