一种求质数的高效算法的实现差异及数学证明

Question

当我学习梁的Java编程入门书时，我被困在了一个点上。问题是如何有效地找到质数。

为了找出n是否为素数，我们必须检查n是否能被数2、3、4、…、sqrt(n)整除。

我们可以通过检查n是否能被数字2、3、4、…、floor(sqrt(n))整除来提高算法的效率。

例如，36到48之间的数字，它们的(int)(Math.sqrt(number))是6。但是，根据下面的程序，对于number=40，平方根是7，而不是6。即，根据数学证明，我们通过检验40是否能被2,3,4,5,6整除来检验40是否为素数。根据下面的程序，我们通过检查40是否能被2、3、4、5、6、7整除来检验40是否为素数。这就是矛盾。我不明白。请帮助。

下面是实现这个问题的算法:

import java.util.Scanner;
public class EfficientPrimeNumbers {
  public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    System.out.print("Find all prime numbers <= n, enter n: ");
    int n = input.nextInt();
    // A list to hold prime numbers
    java.util.List<Integer> list = 
      new java.util.ArrayList<Integer>(); 
    final int NUMBER_PER_LINE = 10; // Display 10 per line
    int count = 0; // Count the number of prime numbers
    int number = 2; // A number to be tested for primeness
    int squareRoot = 1; // Check whether number <= squareRoot
    System.out.println("The prime numbers are n");
    // Repeatedly find prime numbers
    while (number <= n) {
      // Assume the number is prime
      boolean isPrime = true; // Is the current number prime?
      if (squareRoot * squareRoot < number) squareRoot++;
      // For numbers between 36 and 48, squareRoot is 7 which contradicts with the matematical proof.!!!
      // ClosestPair if number is prime
      for (int k = 0; k < list.size() 
                        && list.get(k) <= squareRoot; k++) {
        if (number % list.get(k) == 0) { // If true, not prime
          isPrime = false; // Set isPrime to false          
          break; // Exit the for loop
        }
      }
      // Print the prime number and increase the count
      if (isPrime) {
        count++; // Increase the count
        list.add(number); // Add a new prime to the list
        if (count % NUMBER_PER_LINE == 0) {
          // Print the number and advance to the new line
          System.out.println(number);
        }
        else
          System.out.print(number + " ");
      }
      // Check if the next number is prime
      number++;
    }
    System.out.println("n" + count + 
      " prime(s) less than or equal to " + n);
  }
}

Answer 1

程序只检查小于或等于sqrt(number) + 1的素数的可整除性。一旦检测到素数，它将被添加到list对象中:

if (isPrime) {
    count++; // Increase the count
    list.add(number); // Add a new prime to the list

在这里检查列表中数字的可整除性:

for (int k = 0; k < list.size() && list.get(k) <= squareRoot; k++) {
    if (number % list.get(k) == 0) { // If true, not prime

所以对于36和48之间的数字，它检查2, 3, 5, 7，这实际上比2, 3, 4, 5, 6好。渐近地，它们仍然是相同的，但在实践中，您可以通过仅检查质数的可整除性来节省一些工作。

事实上，由于您描述的原因，您可以保存操作并将list.get(k) <= squareRoot中的<=更改为<。然后，它甚至不会为36和48之间的数字操心7，它将更接近你的理论。