Go语言视频零基础入门到精通

nkweew

除了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，判断其是否素数。

程序：

public class TestF{
   public static void main(String args[]){
    long  prime;
    for(long i=3;i<=400;i=i+2){
        if(isSuShu(i)){
            
            if(isSuShu(prime=i*i+4)){
             System.out.println(prime+" = 2 * 2 + " + i + "* " +i);
            }
       }
     }
    }
   /**  
     * 是素数  
     */  
    public static boolean isSuShu(long n) {   
        boolean isSuShu = true;   
        if (n == 1 || n == 2)   
            return true;   
        for (long i = 2; i < Math.sqrt(n) + 1; i += 1) {   
            if (n % i == 0) {   
                return false;   
            }   
        }   
        if (isSuShu == true)   
            return true;   
        else  
            return false;   
    }   
}
运行：
C:\java>java   TestF
13 = 2 * 2 + 3* 3
29 = 2 * 2 + 5* 5
53 = 2 * 2 + 7* 7
173 = 2 * 2 + 13* 13
293 = 2 * 2 + 17* 17
1373 = 2 * 2 + 37* 37
2213 = 2 * 2 + 47* 47
4493 = 2 * 2 + 67* 67
5333 = 2 * 2 + 73* 73
9413 = 2 * 2 + 97* 97
10613 = 2 * 2 + 103* 103
18773 = 2 * 2 + 137* 137
26573 = 2 * 2 + 163* 163
27893 = 2 * 2 + 167* 167
37253 = 2 * 2 + 193* 193
54293 = 2 * 2 + 233* 233
76733 = 2 * 2 + 277* 277
85853 = 2 * 2 + 293* 293
94253 = 2 * 2 + 307* 307
97973 = 2 * 2 + 313* 313
100493 = 2 * 2 + 317* 317
120413 = 2 * 2 + 347* 347
139133 = 2 * 2 + 373* 373

结论：

  运行程序会发现，除“29=2*2+5*5”以外，算出来的所有的费尔马“二平方”素数个位数字都是3，相应Y的个位数字都是3或7。费尔马“二平方”素数分布也很耐人寻味...

   费尔马“二平方”素数太少了，40亿内才718个(10万以内的，符合条件的也就只有 20个)，千万分之二还不到呢。随着数的范围的增大，似乎越来越稀少，但再往后永远是这样吗？会不会在某个范围内反而又稠密起来呢？费尔马“二平方”素数是无穷多个呢，还是有限多个呢？如果是有限个，又是多少个呢？最大的一个又是什么数呢？这些问题的证明可能很简单，也许很复杂，真说不定会成为像“哥德巴赫猜想”那样的谜呢！