我不明白 Java 中质数验证的这个"for"循环

Question

我不理解Java 中的"for"循环

这个循环只是检查一个数字是否素数。我理解第一个语句，因为1不是素数，但它是"for"语句中发生的情况。为什么"素数"被二除，为什么第二个"如果"计算的余数为零？这个代码如何帮助确认素数？它在做什么？

public static boolean isPrime (int primeNumber) {
    if (primeNumber == 1) {
        return false;
    }
    for (int primeDivider=2; primeDivider <= primeNumber/2; primeDivider++) {
        if (primeNumber % primeDivider == 0) {
            return false;
        }
    }
    return true;
}

Answer 1

素数只能被自身和一整除。7是素数，因为只有1和7除以7。8也不是素数，因为除了1和8之外，2和4都被分成8。

查看for循环，看看primeDivider取什么值：2、3、4、5。。。循环依次尝试其中的每一个，看看它是否划分为您正在测试的数字。如果它等分，余数为0，则被测数字不是素数，该方法返回false。如果没有一个数字除，则被测试的数字为素数，该方法返回true。顺便说一句，primeNumber是一个糟糕的变量名。像possiblePrime这样的东西会更好。正在测试的数字可能不是素数。

primeDivider序列在被测数字的一半处停止。如果一个数不是素数（一个复数），那么它的至少一个除数保证小于或等于这个数的一半。

正如其他人所说，这不是一个非常有效的测试。这里有一个稍微高效的版本供您研究：

public static boolean isPrime (int possiblePrime) {
  // Test negatives, zero and 1.
  if (possiblePrime <= 1) {
    return false;
  }
  // Test even numbers
  if (possiblePrime % 2 == 0) {
    // 2 is the only even prime.
    return possiblePrime == 2;
  } 
  // Test odd numbers >= 3.
  int limit = possiblePrime / 2;
  for (int primeDivider = 3; primeDivider <= limit; primeDivider += 2) {
    if (possiblePrime % primeDivider == 0) {
      return false;
    }
  }
  // Only prime numbers reach this point.
  return true;
}

通过分别处理奇数和偶数，您可以通过一次测试捕获所有偶数，并通过每次将primeDivider步进2，将奇数所需的时间大致减半。

正如billjamesdev所说，使用可以提高效率

int limit = (int)Math.floor( Math.sqrt( possiblePrime ));

一个复合数总是有一个除数，而不是1，小于或等于它的平方根。