今天之所以想讲关于求质数的算法，完全跟这条题目有关，看到题目的朋友一定现
在已经有了思路了吧，不过下面的讲解会让你很郁闷，hoho，带上你的思维，跟着
我来

第一，分析题目 排除10000以内，就是求一个质数满足其的值等于两个质数的平方
和就是要满足

K= A^2 + B^2 这个要求，其中A，B是质数，K当然是要求的质数，那好解法可以这
样求一个质数，然后再求出另一个不同的，为什么不同，要是相同 K>2的话，K肯
定不质数了，好然后再平方啊，再来相加，最后再验证所得的K是不质数了，结果
出来，说实话，当你等待了N秒之后发现结构仍然没有出来之后的时候你会觉得自己
的算法该优化了，其实我开始是这么想的，结果。。。

好，说说我的想法 ，讲点数学吧

(1) (A + B)^2 = A^2 + 2*AB + B^2 ,”平方和”与”和的平方的”转换公式

(2)奇偶公式:
两个偶数之和是偶数，两个偶数之积是偶数
两个奇数之和是偶数，两个奇数之积是奇数
一个奇数和一个偶数之和是奇数，之积是偶数
(3)哥德巴赫猜想：任意两个大于2素数之和是偶数

第三条很重要，虽然是猜想，但是在计算机科学可以计算的数据大小类是可以证明
的，穷举法嘛

数学说完，继续我们的算法优化，请继续看下面的分析

K = A^2 + B^2 => K = (A + B)^2 - 2*AB

因为A + B是偶数（哥德巴赫猜想），那么(A + B)^2也是偶数，K是质数，如果K != 2
那么K肯定是奇数，为什么？这个我就不解释了，继续推导

K是奇数，(A + B)^2是偶数，那么 2*AB就一定是偶数，2乘以一个数的话，肯定是
偶数了，偶数加偶数是偶数，但是K是质数啊，不偶数啊，为什呢？，那么，可以肯
定A，B当中肯定有一个数符合特殊情况，比如1，2

那么， 如果 A = B = 1 ， K = 2，符合要求
如果 A ，B当中一个为1 ， 那么举个反例 A = 1 ，B = 3，K=10 不符合
要求，而且，奇数的平方是奇数，那么这个奇数加1肯定是偶数了，偶数还提什么
素数干嘛呢
如果A = B = 2 ，K = 8 ， 不符合
所以，A，B符合一种情况 A ，B当中必定有一个数为2，另一个数为另一个
质数，单独考虑1，2的情况K=5，符合条件。

综上，K的集合{2 , 5}加上其他符合一个质数2为，另一个为除1，2外其它质数，

所以算法可以优化成

K = 4 + B^2 这回简单了吧

算法如下(算法描述语言)：
算法复杂度O(N),还可以优化到O(SQRT(N))
加上判断是否是质数的算法复杂度
结果最坏也就是O(N^2)

相比那个先求两个质数，再平方后求，然后再判断是否是质数的方法来说确实减少
不少消耗

今天之所以想讲关于求质数的算法，完全跟这条题目有关，看到题目的朋友一定现
在已经有了思路了吧，不过下面的讲解会让你很郁闷，hoho，带上你的思维，跟着
我来

第一，分析题目 排除10000以内，就是求一个质数满足其的值等于两个质数的平方
和就是要满足

K= A^2 + B^2 这个要求，其中A，B是质数，K当然是要求的质数，那好解法可以这
样求一个质数，然后再求出另一个不同的，为什么不同，要是相同 K>2的话，K肯
定不质数了，好然后再平方啊，再来相加，最后再验证所得的K是不质数了，结果
出来，说实话，当你等待了N秒之后发现结构仍然没有出来之后的时候你会觉得自己
的算法该优化了，其实我开始是这么想的，结果。。。

好，说说我的想法 ，讲点数学吧

(1) (A + B)^2 = A^2 + 2*AB + B^2 ,”平方和”与”和的平方的”转换公式

(2)奇偶公式:
两个偶数之和是偶数，两个偶数之积是偶数
两个奇数之和是偶数，两个奇数之积是奇数
一个奇数和一个偶数之和是奇数，之积是偶数
(3)哥德巴赫猜想：任意两个大于2素数之和是偶数

第三条很重要，虽然是猜想，但是在计算机科学可以计算的数据大小类是可以证明
的，穷举法嘛

数学说完，继续我们的算法优化，请继续看下面的分析

K = A^2 + B^2 => K = (A + B)^2 - 2*AB

因为A + B是偶数（哥德巴赫猜想），那么(A + B)^2也是偶数，K是质数，如果K != 2
那么K肯定是奇数，为什么？这个我就不解释了，继续推导

K是奇数，(A + B)^2是偶数，那么 2*AB就一定是偶数，2乘以一个数的话，肯定是
偶数了，偶数加偶数是偶数，但是K是质数啊，不偶数啊，为什呢？，那么，可以肯
定A，B当中肯定有一个数符合特殊情况，比如1，2

那么， 如果 A = B = 1 ， K = 2，符合要求
如果 A ，B当中一个为1 ， 那么举个反例 A = 1 ，B = 3，K=10 不符合
要求，而且，奇数的平方是奇数，那么这个奇数加1肯定是偶数了，偶数还提什么
素数干嘛呢
如果A = B = 2 ，K = 8 ， 不符合
所以，A，B符合一种情况 A ，B当中必定有一个数为2，另一个数为另一个
质数，单独考虑1，2的情况K=5，符合条件。

综上，K的集合{2 , 5}加上其他符合一个质数2为，另一个为除1，2外其它质数，

所以算法可以优化成

K = 4 + B^2 这回简单了吧

算法如下(算法描述语言)：
算法复杂度O(N),还可以优化到O(SQRT(N))
加上判断是否是质数的算法复杂度
结果最坏也就是O(N^2)

相比那个先求两个质数，再平方后求，然后再判断是否是质数的方法来说确实减少
不少消耗

//isPrime()判断数是否是素数
int N = 10000
int i;
for i = 3 to sqrt(N)
	if isPrime( i^2 + 4)
		return(i^2 + 4)
	else
		i = i + 1