查找给定范围内素数的Java程序：

Question

我正在开发一个 Java 程序来查找给定范围内的所有素数。该程序应采用两个整数作为输入（开始和结束）并打印该范围内的素数。这是我到目前为止所拥有的：

import java.util.Scanner;

public class PrimeNumberFinder {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the starting number: ");
        int start = scanner.nextInt();

        System.out.print("Enter the ending number: ");
        int end = scanner.nextInt();

        System.out.println("Prime numbers between " + start + " and " + end + " are:");
        printPrimeNumbers(start, end);
    }

    // Function to check if a number is prime
    private static boolean isPrime(int num) {
        if (num <= 1) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    // Function to print prime numbers in a given range
    private static void printPrimeNumbers(int start, int end) {
        for (int i = start; i <= end; i++) {
            if (isPrime(i)) {
                System.out.print(i + " ");
            }
        }
    }
}

该程序似乎正在运行，但我想知道是否可以进行任何优化或改进。此外，如果有更好的算法来查找素数，我很想了解它们。

Answer 1

简单：计算平方根相对昂贵。不要在循环终止条件下每次都重新计算相同的值。

更深入：如果您已经发现它不是 2 的倍数，则无需（例如）尝试除以 4。因此，保存所有先前的素数并仅除以这些素数。测量结果以确保它更便宜。