判断一个数是否是素数-蒲公英云

判断一个数是否是素数

什么是素数？

素数释义：

曾称质数。一个大于1的正整数，如果除了1和它本身以外，不能被其他正整数整除，就叫素数。如2，3，5，7，11，13，17…。

根据素数定义判断素数

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

从2开始，一直到小于其自身，依次判断能否被n整除即可，能够整除则不是质数，否则是质数。

初步优化

参考算法一书，人民邮电出版社

假如n是合数，必然存在非1的两个约数p1和p2，其中p1<=sqrt(n)，p2>=sqrt(n)

public boolean isPrime(int n) {
    if (n <= 3) {
        return n > 1;
    }
    int sqrt = (int)Math.sqrt(n);
    for (int i = 2; i <= sqrt; i++) {
        if(n % i == 0) {
            return false;
        }
    }
    return true;
}

最终优化

质数还有一个特点，就是它总是等于 6x-1 或者 6x+1，其中 x 是大于等于1的自然数。

6x能被2,3,6整除肯定不是质数

6x+1

6x+2 能被2整除

6x+3 能被3 整除

6x+4 能被2整除

6x+5 等价于6x-1

public static boolean isPrime(int num) {
    if (num <= 3) {
        return num > 1;
    }
    // 不在6的倍数两侧的一定不是质数
    if (num % 6 != 1 && num % 6 != 5) {
        return false;
    }
    int sqrt = (int) Math.sqrt(num);
    for (int i = 5; i <= sqrt; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}