原始检查

Question

每个素数都是6k + 1或6k-1的形式.为了检查数字是否为素数,我们可以使用以下算法.我见过基于这些算法编写的程序.

public boolean isPrime(int n)
{

    if (n <= 1)  return false;
    if (n <= 3)  return true;

    if (n%2 == 0 || n%3 == 0) return false;

    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
           return false;

    return true;
}

但是,如果我们以下列方式编写代码,我不明白会出现什么问题:

public boolean isPrime(int number){
        boolean primeFlag = false;
        if(number == 0 || number ==1){
            return primeFlag;
        }
        if(number == 2 || number == 3){
            primeFlag = true;
        }
        if((number+1)%6 == 0){
            primeFlag = true;
        }
        if((number-1)%6 == 0){
            primeFlag = true;
        }
        return primeFlag;
    }

通过这种方式,与O(root(n))相比,我们可以将时间复杂度降低到O(1).如果我朝错误的方向走,请告诉我.

Answer 1

可以说每个素数(除了2和3)在除以6时都有1或5的余数(有关更深入的解释,请参阅本页).然而,事实恰恰相反.当除以6时,并非每个余数为1或5的数字都是素数.

以35为例.当除以6时,它的余数为5,但它不是素数(35 = 5 x 7).