【数据结构与算法】素数 判定

判定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;
    }