2006-01-12
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个)，千万分之二还不到呢。随着数的范围的增大，似乎越来越稀少，但再往后永远是这样吗？会不会在某个范围内反而又稠密起来呢？费尔马“二平方”素数是无穷多个呢，还是有限多个呢？如果是有限个，又是多少个呢？最大的一个又是什么数呢？这些问题的证明可能很简单，也许很复杂，真说不定会成为像“哥德巴赫猜想”那样的谜呢！
评论