Очень простой простой номер теста - я думаю, что я не понимаю цикл for

Я практикую прошлые экзаменационные документы для базового экзамена по Java, и мне трудно сделать работу цикла для проверки того, является ли число простым. Я не хочу усложнять его, добавляя меры эффективности для больших чисел, просто что-то, что, по крайней мере, будет работать для двухзначных чисел.

В настоящий момент он всегда возвращает false, даже если n - простое число.

Я думаю, что моя проблема в том, что я получаю что-то не так в самом цикле for и где поставить "return true"; и "return false",... Я уверен, что это действительно основная ошибка, которую я делаю...

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

Причина, по которой я не мог найти помощь в другом месте в stackoverflow, заключается в том, что аналогичные вопросы требовали более сложной реализации, чтобы иметь более эффективный способ сделать это.

Ответы

Ответ 1

У вашего цикла for есть небольшая проблема. Это должно быть: -

for (i = 2; i < n; i++)  // replace `i <= n` with `i < n`

Конечно, вы не хотите проверять остаток, когда n делится на n. Это всегда даст вам 0.

Фактически, вы можете даже уменьшить количество итераций, изменив условие на: - i <= n / 2. Поскольку n нельзя разделить на число, большее, чем n / 2, за исключением случаев, когда мы рассматриваем n, что мы не должны рассматривать вообще.

Итак, вы можете изменить цикл for на: -

for (i = 2; i <= n / 2; i++)

Ответ 2

Вы можете остановиться намного раньше и быстрее пропустить цикл:

public boolean isPrime(long n) {
    // fast even test.
    if(n > 2 && (n & 1) == 0)
       return false;
    // only odd factors need to be tested up to n^0.5
    for(int i = 3; i * i <= n; i += 2)
        if (n % i == 0) 
            return false;
    return true;
}

Ответ 3

Вы должны написать i < n, потому что последний шаг итерации даст вам true.

Ответ 4

Ошибка: я <= n

for (i = 2; i<n; i++){

Ответ 5

public class PrimeNumberCheck {
  private static int maxNumberToCheck = 100;

  public PrimeNumberCheck() {
  }

    public static void main(String[] args) {
      PrimeNumberCheck primeNumberCheck = new PrimeNumberCheck();

      for(int ii=0;ii < maxNumberToCheck; ii++) {
        boolean isPrimeNumber = primeNumberCheck.isPrime(ii);

      System.out.println(ii + " is " + (isPrimeNumber == true ? "prime." : "not prime."));
    }
  }

  private boolean isPrime(int numberToCheck) {    
    boolean isPrime = true;

    if(numberToCheck < 2) {
      isPrime = false;
    }

    for(int ii=2;ii<numberToCheck;ii++) {
      if(numberToCheck%ii == 0) {
        isPrime = false;
        break;
      }
    }

    return isPrime;
  }
}

Ответ 6

С этим номером кода, делящимся на 3, будет пропущена инициализация кода цикла.
Итерация цикла также пропустит кратные 3.

private static boolean isPrime(int n) {

    if ((n > 2 && (n & 1) == 0) // check is it even
       || n <= 1  //check for -ve
       || (n > 3 && (n % 3 ==  0))) {  //check for 3 divisiable
            return false;
    }

    int maxLookup = (int) Math.sqrt(n);
    for (int i = 3; (i+2) <= maxLookup; i = i + 6) {
        if (n % (i+2) == 0 || n % (i+4) == 0) {
            return false;
        }
    }
    return true;
}

Ответ 7

Вы также можете использовать некоторое простое свойство Math для этого в цикле for.

Число "n" будет простым числом тогда и только тогда, когда оно делится само по себе или 1. Если число не является простым числом, оно будет иметь два фактора:

n = a * b

вы можете использовать цикл for для проверки до sqrt числа "n" , а не для перехода на "n" . Как и в случае, если "a" и "b" оба больше, чем sqrt числа "n" , a * b будет больше, чем "n" . Таким образом, по крайней мере один из факторов должен быть меньше или равен квадратному корню.

поэтому ваш цикл будет выглядеть следующим образом:

for(int i=2; i<=Math.sqrt(n); i++)

Сделав это, вы резко уменьшите сложность кода во время выполнения. Я думаю, что это сведется к O (n/2).

Ответ 8

Одним из самых быстрых способов является цикл только до квадратного корня из n.

  private static boolean isPrime(int n){
        int square = (int)Math.ceil((Math.sqrt(n)));//find the square root
        HashSet<Integer> nos = new HashSet<>(); 
        for(int i=1;i<=square;i++){
            if(n%i==0){
                if(n/i==i){
                    nos.add(i);
                }else{
                    nos.add(i);
                    int rem = n/i;
                    nos.add(rem);
                }
            }
        }
        return nos.size()==2;//if contains 1 and n then prime
    }

Ответ 9

Вы проверяете i<=n. Так что, когда i==n, вы получите только 0, и он вернет false always.Try i<=(n/2). Нет необходимости проверять до i<n.

Ответ 10

Вышеупомянутый алгоритм рассматривает 1 как простое, хотя это не так. Следовательно, это решение.

static boolean isPrime(int n) {
  int perfect_modulo = 0;
  boolean prime = false;

  for ( int i = 1; i <=  n; i++ ) {
    if ( n % i == 0 ) {
      perfect_modulo += 1;
    }
  }
  if ( perfect_modulo == 2 ) {
    prime = true;
  }

  return prime;
}