Метод поиска простых чисел

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) Не объявляйте булево вернуться, так как вы уже возвращает истину или ложь во всем коде. Удалите эту строку из кода (назовем его [1]):

boolean prime = false; 

Вы поймете, почему после того, как вы исправили остальную часть вашей функции.Прокомментируйте это, если хотите, пока.

2) В вашем втором else if, давайте назовем его [2], у вас есть:

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

Вы уже проверили if nbTest is 2 в своем первом else if, так что вам не нужно, чтобы проверить, если это не 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; 
} 

Таким образом, возвращение ложным. Это не число. И функция не продолжает выполняться. Ваша ошибка продолжалась после того, как функция обнаружила, что ваш ввод не является простым.

Наконец, вы можете оставить свой return true в конце тела функции. Если функция никогда не возвращалась из предыдущих тестов или из цикла, это должно быть простое число. Помните, что в первой строке я сказал вам удалить? Булевская декларация? Поскольку вы никогда не возвращаете значение из переменной, вы просто возвращаете true или false, вам не нужна эта строка [1].

В качестве дополнительного, хорошо читать по поиску простых чисел, которые вы могли бы хотеть, чтобы поделиться с профессором:

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

Answer 2

Вы должны остановиться, как только вы здесь:

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

Answer 3

вы не должны 't продолжать тестирование для primality, как только значение prime было установлено на false для числа.

Заменить:

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

Неправильная для вашего цикла.

Простое число - это число, которое делится на 1 и только на себя. Итак, если число A делится на любое другое число, кроме 1 и самого себя, то A является непервичным.

Просто заменить ваш цикл с одним ниже

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

После того, как было установлено, что nbTest делится на некоторое число, то не указывают на продолжение цикла. Return `nbTest не является приоритетным, тогда и там.