素性检查

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 的说法是正确的（请参阅 this page 以获得更深入的解释）。然而，事实并非如此。并非所有除以 6 后余数为 1 或 5 的数都是质数。

以35为例。它除以 6 的余数为 5，但它不是质数 (35 = 5 x 7)。