【資料結構與算法】素數 判定

判定n是不是素數

素數的判定，如果隻能被1和本身整除，這個數就是素數。特别地，1既不是素數也不是合數。

思路一：從2-n依次判定是不是能整除n；

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

提升：其實不用2-n，隻要2-n^(1/2)即可；

public boolean isPrime2(int n) {
        if (n <= 1)
            return false;
        int max = (int) Math.pow(n, 0.5);
        for (int i = 2; i <= max; i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }
           

提升：把開方優化為乘法運算；

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

提升：如果已經判定過不能被2整除，那麼所有2的倍數，即2k也不需要判定了，因為如果能被2k整除，也一定能被2整除。這樣可以删除一半的數目；注意，這裡其實還隐藏了一個小技巧，就是無需判定i是否是2的倍數，而是直接i+=2，使用步長代替判定。

public boolean isPrime4(int n) {
        if (n <= 1)
            return false;
        if (n == 2)
            return true;
        if (n % 2 == 0)
            return false;
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0)
                return false;
        }
        return true;
    }
           

提升：同樣的還可以把3考慮進去。如果更深入一些，可以利用一個事實，2*3=6，即6的倍數裡面，隻有6k+1或者6k-1需要判定，其餘的都是2或者3的倍數。

https://www.geeksforgeeks.org/java-program-to-check-if-a-number-is-prime-or-not/

public boolean isPrime5(int n) {
        if (n <= 1)
            return false;
        if (n == 2 || n == 3)
            return true;
        if (n % 2 == 0 || n % 3 == 0)
            return false;
        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
        }
        return true;
    }
           

延伸：可以考慮所有前面的素數的乘積。比如：p=p1*p2*p3....。每一個都是小于等于n開平方的素數，然後根據每一個pi的倍數，挑選出p區間内的需要判定的數字。6=2*3就是特例。

另外還有一個變種，找出小于n的所有素數：

用的是一個标記法，把找到的所有的素數的倍數标記，剩下的就是素數了。

public int countPrimes(int n) {
        int count = 0;

        if (n <= 1)
            return count;

        int[] mark = new int[n];
        for (int i = 2; i * i < n; i++) {
            if (mark[i] > 0)
                continue;
            for (int j = i; i * j < n; j++) {
                mark[i * j] = 1;
            }
        }
        for (int i = 2; i < n; i++)
            if (mark[i] == 0)
                count++;
        return count;
    }