Java 数组保存素数并用它来寻找下一个素数

Question

我在理解老师要我做什么时遇到了一个小问题。我所做的是一个代码，可以将所有素数保存在一个可以显示的数组中。但现在他要我 "optimize" 代码，据我所知，尝试将一个数除以质数。例如：如果我有 2、3、5，下一个素数就是不能除以其中任何一个的数。所以我不必尝试 2、3、4、5，而只需尝试 2、3、5（数组中的数字）。例如：2,3,4,5,7 是质数，10 不是，因为它除以 2 然后它必须跳到下一个数字。

public static void main(String[] args) {
    String introducedNumber = JOptionPane.showInputDialog("Introduce a number"); //with JOptionPane imported will ask you a small box for a number
    int number, divider, numberDividing; //declaring the int's

    number = Integer.parseInt(introducedNumber); //converting the input to a int
    int x = 0; //starting X to 0 since its 1st array position
    int[] arrayPrime = new int[number]; //declaring and creating an array
    for (divider = 1; divider <= number; divider++) { //for to run till numbers
        //for that checks if the number divides by any other than himself
        for (numberDividing = 2; (numberDividing < divider) && (divider % numberDividing != 0); numberDividing++) {
        }

        if (numberDividing >= divider) {
            arrayPrime[x] = divider;
            x++;
        }
    }
    for (int i = 0; i < x; i++) {
        System.out.println(arrayPrime[i]);
    }

}

}

Answer 1

目前检查数字是否为质数的代码是：

    for (numberDividing = 2; (numberDividing < divider) && (divider % numberDividing != 0); numberDividing++) {
    }

    if (numberDividing >= divider) {
        arrayPrime[x] = divider;
        x++;
    }

所以它正在检查从 2 到最后一个素数的所有数字。但它没有必要这样做：它只需要检查数组中已有的素数。

为了使您的代码更具可读性，我建议将您的检查移至单独的私有方法。我还将 x 重命名为 primeCount:

private boolean isPrime(int number) {
    for (int i = 0; i < primeCount; i++) {
        if (number % arrayPrime[i] == 0)
            return false;
    }
    return true;
}

那么你的调用代码就变成了：

for (int divider = 2; divider <= number; divider++) {
    if (isPrime(divider))
        arrayPrime[primeCount++] = divider;
}

您还可以进行另一个相当简单的优化。您不需要检查任何大于测试数平方根的素数，因为此时您已经检查了更小的因子：

private boolean isPrime(int number) {
    for (int i = 0; i < primeCount; i++) {
        int prime = arrayPrime[i];
        if (prime * prime > number)
            break;
        else if (number % prime == 0)
            return false;
    }
    return true;
}

如果您不想使用单独的方法，则：

for (int divider = 2; divider <= number; divider++) {
    boolean isPrime = true;
    for (int i = 0; i < primeCount && isPrime; i++) {
        isPrime = number % arrayPrime[i] > 0;
    }
    if (isPrime)
        arrayPrime[primeCount++] = divider;
}

并且，为了您以后的学习，这里有一种使用质数生成器实现相同结果的更优雅的方法：

public class PrimeGenerator {
    private long current = 1;
    private final List<Long> primes = new ArrayList<>();

    public long next() {
        do {
            current++;
        } while (primes.stream().anyMatch(n -> current % n == 0));
        primes.add(current);
        return current;
    }
}

Answer 2

你是对的，你只需要将新数字除以以前发现的素数。我在下面所做的只是循环遍历所有发现的素数，并使用布尔值来跟踪每个数字是否为素数。我还使用 ArrayList 而不是数组，这样就不会像原始数组中那样有很多未使用的块。希望这可以帮助！

ArrayList<Integer> arrayPrime = new ArrayList<Integer>(); //use array list instead of static array
arrayPrime.add(2); //seed first prime number
boolean isPrime; //boolean to determine if prime

for (divider = 3; divider <= number; divider++) { //loop up to input number, starting at 3

    isPrime = true; //initialize true for each new number

    for (i = 0; i < arrayPrime.size(); i++) { //loop through each previous prime

        if (divider % arrayPrime[i] == 0) { //see if number is divisible by previous prime
            isPrime = false;
            break; //break out of loop
        }
    }

    if(isPrime){ //if it did not divide evenly, it is prime
        ArrayPrime.add(divider);
    }
}

System.out.println(list);

Java 数组保存素数并用它来寻找下一个素数

Java Array saving prime numbers and using it to find next prime

java

arrays

math

primes

numbers