李大仁博客

一条学校的ACM演练题目，很让人郁闷

今天之所以想讲关于求质数的算法，完全跟这条题目有关，看到题目的朋友一定现在已经有了思路了吧，不过下面的讲解会让你很郁闷，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