爲什麼我的程序認爲4是一個素數？

Question

任何想法爲什麼這個方法爲'4'返回true？

private boolean isPrime(int num) { 
      if (num < 2) { 
       return false; 
      } 
      for (int i = 2; i < num/2; i++) { 
       if (num % i == 0) 
        return false; 
      } 
      return true; 
} 

Answer 1

，因爲你的循環從2開始，在num/2 -1這在num = 4的情況下1結束返回TRUE。這意味着你永遠不會進入for循環。

你for迴路應

for (int i = 2; i <= num/2; i++) 

注意，你的循環運行時間將O(num)。對於更高的效率，你可能要考慮循環

for (int i = 2; i * i <= num; i++) 

這是O(sqrt(num))。

Answer 2

它正在返回true因爲控制永遠不會進入for循環內部。

for(int i = 2; i < num/2; i++) { ... } 

這裏num是4然後num/2將2

for(int i = 2; i < 2; i++) { ... } 

，最初我是2這是不小於2。所以i < 2會給假。
所以你的循環永遠不會運行。並且函數將返回true

Answer 3

更有效的解決方案是檢查2後跟奇數到sqrt（n），因爲上面的任何數字都意味着有一個小於這個的因子。

static boolean isPrime(long num) { 
    if (num < 2) return false; 
    if (num == 2) return true; 
    if ((num & 1) == 0) return false; // must be even 
    for (int i = 3, max = (int) Math.sqrt(num); i <= max; i += 2) 
     if (num % i == 0) 
      return false; 
    return true; 
}