2006-01-12 费尔马“二平方”素数（java实现）TAG：Java除了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=X*X+Y*Y(1)，其中F、X、Y都是素数，它就是费尔马“二平方”素数。编程思路：求42亿之内(例程只算了10万以内的)的费尔马“二平方”素数。如果按定义从左向右，先求一个素数F，然后再去找相应的素数X、Y，工作量重复太大。我们可以对上述公式进行分析：1、左侧素数F肯定是奇数，那么右侧两个素数的和也应该是奇数，所以X和Y为一奇一偶(奇数的平方还是奇数，偶数的平方还是偶数)。X、Y要求是素数，而既是偶数又是素数的数只有一个――2，这样我们就可以确定其中一个为2(这里设X=2)。所以(1)式可以简化为：F=2*2+Y*Y(2)，费尔马“二平方”素数的表示形式是惟一的。2、按(2)式由大到小找素数Y，计算出加上4(2*2)后是否等于F，判断其是否素数。3、求出素数Y后将其保存起来，在判断其它数是否素数时可直接用已求出的素数去除，如此反复。算法源代码如下：public class Test {static int n = 0, c = 0;static int[] a = new int[10000];static void ScreenOut(long prime) {int p;for (p = c - 1; p> 0; p--) {if (prime == (a[p] * a[p] + 4)) {System.out.println(prime + " = 2 * 2 + " + a[p] + "* " + a[p]);n++;}}}public static void main(String[] args) {int i, count, quantity = 100000;boolean judgement;a[0] = 2;for (count = 3; count< quantity; count += 2) {judgement = true;for (i = 3; i< count / 2; i++) {if (count % i == 0) {judgement = false;break;}}if (judgement) {a[++c] = count;ScreenOut(count);}}System.out.println("\ntotal of match: " + n);}}结论：运行程序会发现，除“29=2*2+5*5”以外，算出来的所有的费尔马“二平方”素数个位数字都是3，相应Y的个位数字都是3或7。费尔马“二平方”素数分布(修改程序中变量x的值得到)也很耐人寻味...费尔马“二平方”素数太少了，40亿内才718个(10万以内的，符合条件的也就只有20个)，千万分之二还不到呢。随着数的范围的增大，似乎越来越稀少，但再往后永远是这样吗？会不会在某个范围内反而又稠密起来呢？费尔马“二平方”素数是无穷多个呢，还是有限多个呢？如果是有限个，又是多少个呢？最大的一个又是什么数呢？这些问题的证明可能很简单，也许很复杂，真说不定会成为像“哥德巴赫猜想”那样的谜呢！

评论