請解釋審判庭如何工作的素性測試

Question

我碰到這個算法測試素性通過審判庭我完全理解這種算法

static boolean isPrime(int N) { 
    if (N < 2) 
     return false; 
    for (int i = 2; i <= Math.sqrt(N); i++) 
     if (N % i == 0) 
      return false; 
    return true; 
} 

它工作得很好。但後來我發現了另一個效果很好的另一個，但我並不完全理解它背後的邏輯。

static boolean isPrime(int N) { 
    if (N < 2) 
     return false; 
    for (int i = 2; i * i<N; i++) 
     if (N % i == 0) 
      return false; 
    return true; 
} 

好像i *i < N行爲就像i <= Math.sqrt(N)。如果是這樣，爲什麼？

Answer 1

是的，你是對的，那些是相同的，如果你把第一個方程的兩個部分平方，明顯的方程式i <= Math.sqrt(N)可以被整數改寫爲i * i <= N。
, ，即a < b等於a * a < b * b，對於正a，b;

Answer 2

順便說一句，你可以用一些調整，加快你的代碼，如果你覺得實在是太慢了：

static boolean isPrime(int N) { 
    if (N <= 1) 
     return false; 
    if (N % 2 == 0) 
     return N == 2; 
    for (int i = 3; i <= Math.sqrt(N); i += 2) 
     if (N % i == 0) 
      return false; 
    return true; 
} 

這個版本確實爲陰性和可分2特殊測試，然後只能通過劃分從那時起的奇數：3,5,7，...（注意「+ = 2」）。