對于一個大于1的整數(shù)，如果其除數(shù)只有1和它本身，那么它就是一個質(zhì)數(shù)

判斷一個數(shù)是否為質(zhì)數(shù)

窮舉法

• 窮舉法，檢測2,3,4,5...,n-1能夠整除n。如果不能，那么n就是素數(shù)。這個算法耗費O(n)來檢測n是否是一個素數(shù)。

public static boolean isPrimeNumber(int n){
        if (n < 2) {
            return false;
        }
        for (int i = 2; i <= n-1; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

時間復(fù)雜度為O(n)

稍微改進的算法

• 稍微注意一下，只需檢測2,3,4,5...n/2是否能整除n。如果不能那么n就是素數(shù)。算法效率只是稍微提高了一點，它的時間復(fù)雜度依舊是O(n)

public static boolean isPrimeNumber1(int n) {
        if (n < 2) {
            return false;
        }
        for (int i = 2; i <= n / 2; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

高效算法

• 實際上我們可以證明，如果n不是素數(shù)，那么n必須有一個大于1且小于或者等于√n。證明過程：
  因為n不是素數(shù)，所以會存在兩個數(shù)p和q，滿足n=pq且1<p≤q。注意到n=√n*√n。p必須小于等于√n。

  因此只需要檢測2,3,4,5,...,√n是否能被n整除。如果不能，n就是素數(shù)。這會顯著的降低時間復(fù)雜度，為O(√n)。

public static boolean isPrimeNumber2(int n) {
        if (n < 2) {
            return false;
        }
        int squareRoot=(int) Math.sqrt(n);
        for (int i = 2; i <= squareRoot; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

上述開根號的效率較低，可以用以下方式代替。

public static boolean isPrimeNumber3(int n) {
        if (n < 2) {
            return false;
        }
        int squareRoot=1;
        while(squareRoot*squareRoot<n){
            squareRoot++;
        }
        for (int i = 2; i  <= squareRoot; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

篩選出小于n內(nèi)所有質(zhì)數(shù)的

上述都是判斷一個大于1的自然數(shù)是否是素數(shù)的算法，對于篩選出小于自然數(shù)n內(nèi)的所有素數(shù)，有一個更為高效的算法，埃拉托斯特尼篩法。這個算法求出所有小于或等于n的素數(shù)。

這個算法的原理是：一個質(zhì)數(shù)總是可以分解成若干個質(zhì)數(shù)的乘積，那么如果把質(zhì)數(shù)（最初只知道2是質(zhì)數(shù)）的倍數(shù)都去掉，那么剩下的就是質(zhì)數(shù)了。

埃拉托斯特尼篩法

算法實現(xiàn)：

/**
     * 運用埃拉托色篩選法篩選出所有小于等于n的質(zhì)數(shù)
     */
    public static boolean[] sieveOfEratosthenes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        //初始化，默認所有都是質(zhì)數(shù)
        for (int i = 0; i <= n; i++) {
            isPrime[i] = true;
        }
        //篩選，將所有質(zhì)數(shù)的倍數(shù)都標記為非質(zhì)數(shù)(最初只知道2是質(zhì)數(shù))
        for (int i = 2; i <= n / i; i++) {
            if (isPrime[i]) {
                for (int j = 2; j <= n/i; j++) {
                    isPrime[i * j] = false;
                }
            }
        }
        return isPrime;
    }

給出總的程序代碼：

/**
 * @author: gethin
 * @create: 2018-06-20 21:40
 * @description:
 **/
public class PrimeNumberJudge {
    
    /**
     * 窮舉法判斷是否為質(zhì)數(shù)，時間復(fù)雜度O(n)
     */
    public static boolean isPrimeNumber(int n) {
        if (n < 2) {
            return false;
        }
        for (int i = 2; i <= n - 1; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
    
    /**
     * 窮舉法稍微改進,時間復(fù)雜度O(n)
     */
    public static boolean isPrimeNumber1(int n) {
        if (n < 2) {
            return false;
        }
        for (int i = 2; i <= n / 2; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
    
    /**
     * 高效算法,時間復(fù)雜度O(√n)
     */
    public static boolean isPrimeNumber2(int n) {
        if (n < 2) {
            return false;
        }
        int squareRoot = (int) Math.sqrt(n);
        for (int i = 2; i <= squareRoot; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
    
    /**
     * 高效算法改進,時間復(fù)雜度O(√n)
     */
    public static boolean isPrimeNumber3(int n) {
        if (n < 2) {
            return false;
        }
        int squareRoot = 1;
        while (squareRoot * squareRoot < n) {
            squareRoot++;
        }
        for (int i = 2; i <= squareRoot; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
    
    /**
     * 運用埃拉托色篩選法篩選出所有小于等于n的質(zhì)數(shù)
     */
    public static boolean[] sieveOfEratosthenes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        //初始化，默認所有都是質(zhì)數(shù)
        for (int i = 0; i <= n; i++) {
            isPrime[i] = true;
        }
        //篩選，將所有質(zhì)數(shù)的倍數(shù)都標記為非質(zhì)數(shù)(最初只知道2是質(zhì)數(shù))
        for (int i = 2; i <= n / i; i++) {
            if (isPrime[i]) {
                for (int j = 2; j <= n / i; j++) {
                    isPrime[i * j] = false;
                }
            }
        }
        return isPrime;
    }
    
    public static void main(String[] args) {
        int count = 0;
        Scanner input = new Scanner(System.in);
        System.out.print("輸入整數(shù)n:");
        int num = input.nextInt();
        System.out.println("\n運用改進的高效算法求小于等于n的所有質(zhì)數(shù)");
        for (int i = 0; i <= num; i++) {
            if (isPrimeNumber1(i)) {
                if (count % 10 == 0) {
                    System.out.println();
                }
                System.out.print(i + "\t");
                count++;
            }
        }
        System.out.println("\n\n運用埃拉托色篩選法求小于等于n的所有質(zhì)數(shù)");
        boolean[] isPrime = sieveOfEratosthenes(num);
        count=0;
        for (int i = 2; i <= num; i++) {
            if (isPrime[i]) {
                if (count % 10 == 0) {
                    System.out.println();
                }
                System.out.print(i + "\t");
                count++;
            }
        }
    }
}