判断素数

在很多编程题里面我们都会用到素数,判断素数已经不再是难题,当判断一系列自然数是否为素数时,算法的时间效率要尽可能高,这里有三种不同效率判断素数的方式:

方法一:          时间复杂度:O(n)



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

这是最直接,最简单的方法

方法二:          时间复杂度:O(sqrt(n))

 



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

 

这是目前用的最多的方法

方法三:           时间复杂度:O(sqrt(n)/2)



public static boolean isPrime(int n){
    if(n == 0||n == 1)
        return false;
    if(n == 2||n == 3)
        return true;
    if(n%6!=1&&n%6!=5)
        return false;
    for (int i = 5; i <= (int) Math.sqrt(n); i+=6)
        if(n%i==0||n%(i+2)==0)
            return false;
    return true;
}

这是目前我见过时间效率最好的一种算法,转自:https://blog.csdn.net/zhanshen112/article/details/90574455


代码编译器:intellij idea 2020.1

您必须 登录 才能发表评论