原始性檢查

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

（1）相比，這一點，我們可以減少時間複雜度至O到O（root（n））。請讓我知道如果朝着錯誤的方向走。

Answer 1

說除了6和6之外，每個素數（2和3除外）都有1或5的餘數是正確的（更深入的解釋請參見this page）。但是，情況正好相反。不是每個數字除以6之後都有1或5的餘數是素數。

以35爲例。它的餘數爲5，除以6，但它不是素數（35 = 5 x 7）。