判断一个数是否是素数

转载java

1.通常写法：web

public static 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;
}

2.优化写法svg

证实：令x≥1，将大于等于5的天然数表示以下：
······ 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ······
能够看到，不在6的倍数两侧，即6x两侧的数为6x+2，6x+3，6x+4，因为2(3x+1)，3(2x+1)，2(3x+2)，因此它们必定不是素数，再除去6x自己，显然，素数要出现只可能出如今6x的相邻两侧。这里有个题外话，关于孪生素数，有兴趣的道友能够再另行了解一下，因为与咱们主题无关，暂且跳过。这里要注意的一点是，在6的倍数相邻两侧并非必定就是质数。
此时判断质数能够6个为单元快进，即将方法（2）循环中i++步长加大为6，加快判断速度，缘由是，假如要断定的数为n，则n一定是6x-1或6x+1的形式，对于循环中6i-1，6i，6i+1,6i+2，6i+3，6i+4，其中若是n能被6i，6i+2，6i+4整除，则n至少得是一个偶数，可是6x-1或6x+1的形式明显是一个奇数，故不成立；另外，若是n能被6i+3整除，则n至少能被3整除，可是6x能被3整除，故6x-1或6x+1（即n）不可能被3整除，故不成立。综上，循环中只须要考虑6i-1和6i+1的状况，即循环的步长能够定为6，每次判断循环变量k和k+2的状况便可，理论上讲总体速度应该会是方法（2）的3倍。代码以下：优化

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