Java實作整型素數的判斷

前言

定義判别法

定義優化判别法

孿生素數性質判别法

 Matlab版素數判别法

後記

前言

        素數判斷的依據是它的定義和它的性質。參考百度百科，素數被定義是一個大于1且隻有1和它本身兩個因數的自然數。而它的性質就非常多了，深入起來也非常之麻煩，在後面的算法實作中，我也隻使用了孿生素數中的一個性質來判斷素數。

定義判别法

        根據素數的定義我們可以利用餘數性質來進行判斷，如果一個數不能整除小于它的任意一個數，那麼它就是素數。其實我們無需從1到n-1開始整除，隻需在2到√n，具體的原因參見：為什麼判斷素數需要周遊到它的平方根？代碼如下：

public static boolean isPrime(int n){
    if(n < 0){
        throw new IllegalArgumentException("N must be a non negative integer.");
    }
    if(n < 4){
        return n > 1;
    }
    for(int i = 2, limit = (int) Math.sqrt(n); i <= limit; i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}
           

定義優化判别法

        其實我們這裡也可以稍微優化，因為除了2以外的偶數，全部都是合數，是以我們可以先判斷n是否為偶數，然後n一定是奇數，接着我們就可以按照3：2：√n來逐個判斷，需要判斷的數量減少。代碼如下：

public static boolean isPrime(int n){
    if(n < 0){
        throw new IllegalArgumentException("N must be a non negative integer.");
    }
    if(n < 4){
        return n > 1;
    }
    if((n & 1) == 0){
        return false;
    }
    for(int i = 3, limit = (int) Math.sqrt(n); i <= limit; i += 2){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}
           

孿生素數性質判别法

        關于孿生素數的判别證明，可以參考這篇部落格：素數（質數）判斷方法。代碼如下：

public static boolean isPrime(int n){
    if(n < 0){
        throw new IllegalArgumentException("N must be a non negative integer.");
    }
    if(n < 4){
        return n > 1;
    }
    int remainder = n % 6;
    if(remainder != 1 && remainder != 5){
        return false;
    }
    for(int i = 5, limit = (int) Math.sqrt(n); i <= limit; i += 6){
        if(n % i == 0 || n % (i + 2) == 0){
            return false;
        }
    }
    return true;
}
           

 Matlab版素數判别法

        Matlab2014a版内置的isprime方法，它是先提取出小于等于√n的所有素數值，然後用n逐個對這些素數求餘，如果有一個求餘不等于0，則說明n為合數，否則n為素數，它的依據主要來自√n的性質。代碼如下：

public static boolean isPrime(int n){
    if(n < 0){
        throw new IllegalArgumentException("N must be a non negative integer.");
    }
    if(n < 4){
        return n > 1;
    }
    for(int prime : primes((int) Math.sqrt(n))){
        if(n % prime == 0){
            return false;
        }
    }
    return true;
}
           

        代碼中的primes方法參見：Java實作快速查找某個範圍内的所有素數。該方法在Java平台可能執行效率不是很高，但是Matlab對矩陣化操作進行了極緻優化，是以在Matlab平台該方法執行效率非常快。可見一個平台上效率高的算法，并不代表在其他語言平台上效率更高，是以在平台上寫算法時，還是要注意相關平台的側重點。

後記

        這篇文章我是對整型範圍的資料進行素數判斷，資料的最大值為2147483647，如果對于超大資料，就應該選擇其他方法，比如Miller_Rabbin素數判别法，具體問題具體分析。