判断一个数是否是质数的算法

对于一个大于1的整数，如果其除数只有1和它本身，那么它就是一个质数

判断一个数是否为质数

穷举法

• 穷举法，检测2,3,4,5...,n-1能够整除n。如果不能，那么n就是素数。这个算法耗费O(n)来检测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;
    }

时间复杂度为O(n)

稍微改进的算法

• 稍微注意一下，只需检测2,3,4,5...n/2是否能整除n。如果不能那么n就是素数。算法效率只是稍微提高了一点，它的时间复杂度依旧是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不是素数，那么n必须有一个大于1且小于或者等于√n。证明过程：
  因为n不是素数，所以会存在两个数p和q，满足n=pq且1<p≤q。注意到n=√n*√n。p必须小于等于√n。

  因此只需要检测2,3,4,5,...,√n是否能被n整除。如果不能，n就是素数。这会显著的降低时间复杂度，为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内所有质数的

上述都是判断一个大于1的自然数是否是素数的算法，对于筛选出小于自然数n内的所有素数，有一个更为高效的算法，埃拉托斯特尼筛法。这个算法求出所有小于或等于n的素数。

这个算法的原理是：一个质数总是可以分解成若干个质数的乘积，那么如果把质数（最初只知道2是质数）的倍数都去掉，那么剩下的就是质数了。

埃拉托斯特尼筛法

算法实现：

/**
     * 运用埃拉托色筛选法筛选出所有小于等于n的质数
     */
    public static boolean[] sieveOfEratosthenes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        //初始化，默认所有都是质数
        for (int i = 0; i <= n; i++) {
            isPrime[i] = true;
        }
        //筛选，将所有质数的倍数都标记为非质数(最初只知道2是质数)
        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 {
    
    /**
     * 穷举法判断是否为质数，时间复杂度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;
    }
    
    /**
     * 穷举法稍微改进,时间复杂度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;
    }
    
    /**
     * 高效算法,时间复杂度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;
    }
    
    /**
     * 高效算法改进,时间复杂度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的质数
     */
    public static boolean[] sieveOfEratosthenes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        //初始化，默认所有都是质数
        for (int i = 0; i <= n; i++) {
            isPrime[i] = true;
        }
        //筛选，将所有质数的倍数都标记为非质数(最初只知道2是质数)
        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("输入整数n:");
        int num = input.nextInt();
        System.out.println("\n运用改进的高效算法求小于等于n的所有质数");
        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的所有质数");
        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++;
            }
        }
    }
}