Java实现整型素数的判断

前言

定义判别法

定义优化判别法

孪生素数性质判别法

 Matlab版素数判别法

后记

前言

        素数判断的依据是它的定义和它的性质。参考百度百科，素数被定义是一个大于1且只有1和它本身两个因数的自然数。而它的性质就非常多了，深入起来也非常之麻烦，在后面的算法实现中，我也只使用了孪生素数中的一个性质来判断素数。

定义判别法

        根据素数的定义我们可以利用余数性质来进行判断，如果一个数不能整除小于它的任意一个数，那么它就是素数。其实我们无需从1到n-1开始整除，只需在2到√n，具体的原因参见：为什么判断素数需要遍历到它的平方根？代码如下：

public static boolean isPrime(int n){
    if(n < 0){
        throw new IllegalArgumentException("N must be a non negative integer.");
    }
    if(n < 4){
        return n > 1;
    }
    for(int i = 2, limit = (int) Math.sqrt(n); i <= limit; i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}
           

定义优化判别法

        其实我们这里也可以稍微优化，因为除了2以外的偶数，全部都是合数，因此我们可以先判断n是否为偶数，然后n一定是奇数，接着我们就可以按照3：2：√n来逐个判断，需要判断的数量减少。代码如下：

public static boolean isPrime(int n){
    if(n < 0){
        throw new IllegalArgumentException("N must be a non negative integer.");
    }
    if(n < 4){
        return n > 1;
    }
    if((n & 1) == 0){
        return false;
    }
    for(int i = 3, limit = (int) Math.sqrt(n); i <= limit; i += 2){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}
           

孪生素数性质判别法

        关于孪生素数的判别证明，可以参考这篇博客：素数（质数）判断方法。代码如下：

public static boolean isPrime(int n){
    if(n < 0){
        throw new IllegalArgumentException("N must be a non negative integer.");
    }
    if(n < 4){
        return n > 1;
    }
    int remainder = n % 6;
    if(remainder != 1 && remainder != 5){
        return false;
    }
    for(int i = 5, limit = (int) Math.sqrt(n); i <= limit; i += 6){
        if(n % i == 0 || n % (i + 2) == 0){
            return false;
        }
    }
    return true;
}
           

 Matlab版素数判别法

        Matlab2014a版内置的isprime方法，它是先提取出小于等于√n的所有素数值，然后用n逐个对这些素数求余，如果有一个求余不等于0，则说明n为合数，否则n为素数，它的依据主要来自√n的性质。代码如下：

public static boolean isPrime(int n){
    if(n < 0){
        throw new IllegalArgumentException("N must be a non negative integer.");
    }
    if(n < 4){
        return n > 1;
    }
    for(int prime : primes((int) Math.sqrt(n))){
        if(n % prime == 0){
            return false;
        }
    }
    return true;
}
           

        代码中的primes方法参见：Java实现快速查找某个范围内的所有素数。该方法在Java平台可能执行效率不是很高，但是Matlab对矩阵化操作进行了极致优化，因此在Matlab平台该方法执行效率非常快。可见一个平台上效率高的算法，并不代表在其他语言平台上效率更高，因此在平台上写算法时，还是要注意相关平台的侧重点。

后记

        这篇文章我是对整型范围的数据进行素数判断，数据的最大值为2147483647，如果对于超大数据，就应该选择其他方法，比如Miller_Rabbin素数判别法，具体问题具体分析。