搜索素數的方法

Question

我需要構建計算素數的方法。

我正在測試它，它給了我錯誤的答案，我不知道如何解決它！例如，它將返回true至98262679而不是false。我的錯誤在哪裏？

public static boolean itsPrime(int nbTest){ // Tests for prime numbers method 

     boolean prime = false; 

     if (nbTest <= 1){ 
      return false; 
     } else if (nbTest == 2){  // Two is prime 
      return true; 
     } else if ((nbTest != 2) && (nbTest % 2 == 0)){  // Evens except number 2 
      return false;          // are not prime 
     } else if (nbTest % 2 != 0){ // For all remaining odds 
      for(int i = 3; i <= Math.sqrt(nbTest); i = i+2){ 
       if (nbTest % i == 0){ 
        prime = false; 
       } else { 
        prime = true; 
       } 
      } 
     } 

     return prime; 
    } 

我學習Java和我的教授要求我們構建方法itsPrime正是基於此：

For the first subtask, write a function `itsPrime` that takes an `int` 
      as argument and returns a `boolean`, `true` if the argument integer is prime 
     and `false` otherwise. 

       To test whether an integer x is prime, one can proceed as follows: 
       all integers less than or equal to 1 are not prime; 
       2 is prime; 
       all other even integers are not prime; 
       for all remaining integers (obviously odd), search for a divisor: 

       loop from 3 to the square root of the integer x (The square root of x can 
    be computed as ‘‘Math.sqrt(x)'' in Java.); if the remainder of the integer 
division of x by the loop index is zero, then x is not prime; 
if all remainders were non-zero at the end of the loop, then x is prime; 

Answer 1

我知道答案在上面所有答案的某處，但我認爲每個答案都需要解釋。

這裏的一切，你可以讓你的代碼的增強的摘要：

1）不要聲明一個布爾返回，因爲你已經在你的代碼返回true或false。從您的這行代碼（稱之爲[1]）：

boolean prime = false; 

你就會明白爲什麼你固定的功能後剩下的。現在，如果需要，請將其評論出來。

2）在第二個else if，姑且稱之爲[2]，您有：

else if ((nbTest != 2) && (nbTest % 2 == 0)){ 
    return false; 
} 

您已經在第一else if檢查if nbTest is 2，這樣你就不會需要檢查，如果它不是2再次。如果它輸入第一個if else，你的函數將返回true。當函數返回時，就完成了。它將值返回給調用者，其餘代碼不會執行。

因此，可以替換第二if else，[2]，具有：

else if (nbTest % 2 == 0) { // all other even integers are not prime 
    return false; 
} 

3）如果輸入第三else if，這意味着該代碼的其餘部分上面已經執行，並且它或者返回，或者程序繼續。

可以更換爲第三else if (nbTest % 2 != 0){：

else { 

4）這是一個錯誤，你真的必須讓你的函數返回錯誤的答案（這個片段[4]）：

if (nbTest % i == 0){ 
    prime = false; 

如果你發現你測試的數字是可分的（即餘數爲零），那麼你就完成了。你一定知道它不是素數。

可以更換這個代碼，[4]，具有：

if(nbTest % counter == 0) { 
    return false; 
} 

因此，返回false。這不是一個數字。並且該函數不會繼續執行。在函數發現你的輸入不是素數之後，你的錯誤繼續執行。

最後，您可以將return true保留在函數體的末尾。如果函數永遠不會從前面的測試或循環中返回，那麼它必須是一個素數。記得我告訴你的第一行刪除？布爾聲明？既然你永遠不會從一個變量中返回一個值，你只需返回true或false，你不需要[1]這一行。

作爲一個額外的，在尋找素數，你可能要與你的教授分享一個良好的閱讀：

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Answer 2

你應該停止在這裏，一旦你：

if (nbTest % i == 0){ 
    return false; 
} 

Answer 3

你不應該一旦素數被設置爲一個數字的假，就不要繼續測試素數。

替換：

if (nbTest % i == 0){ 
    prime = false; 

有：

if (nbTest % i == 0){ 
    return false; 

而最後的測試是沒有用的，你可以只保留一個基本的東西：

else if (nbTest % 2 != 0){ => else { 

Answer 4

刪除prime變量（它是一個不必要的步驟，見下文）。

更改for循環：

for(int i = 3; i <= Math.sqrt(nbTest); i = i+2){ 
    if (nbTest % i == 0){ 
     prime = false; 
    } else { 
     prime = true; 
    } 
} 

要這樣：

for(int i = 3; i <= Math.sqrt(nbTest); i = i+2) 
    if (nbTest % i == 0) 
     return false; 

這只是爆發功能的早期，如果它不是素數（如果一個因素已被發現）。

Answer 5

您的for循環不正確。

素數是一個只能被1整除的數字。因此，如果一個數字A可以被除1和它自身以外的其他數字整除，那麼A是一個非優先數。

一旦發現nbTest是一些數整除下面

for(int i = 3; i <= Math.sqrt(nbTest); i = i+2) { 
    if (nbTest % i == 0) 
     return false; 
} 

的一個只需更換你的for循環，有沒有點在繼續循環。返回`nbTest是非優先的，然後在那裏。