java - 如何记忆一个函数，Eratosthenes 筛法

Question

我正在尝试编写代码，使用埃拉托色尼筛法计算出素数。我必须包含一个函数，该函数将接受一个数字和该数字的所有倍数的交叉。为了测试，我将第一个数字设置为 2，将第二个数字设置为 3。它适用于第一个数字，但不适用于第二个数字(无论数字的顺序如何，即如果我先将 3 放入函数中)。我知道那里还有其他完整的埃拉托色尼筛法，但我想尝试按照我首先想到的方式去做。

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner input = new Scanner(System.in);
    System.out.println("Which number would you like to calculate up to?");
    int n = input.nextInt();
    input.close();

    int x = 0;
    int newNumber = 2;
    int numbers[] = new int[n];
    while(newNumber <= n){
        numbers[x] = newNumber;
        x++;
        newNumber++;
    }

    int currentNumber = 2; 
    int finalNumber[] = markOfMultiples(n, numbers, currentNumber);
    for(int y = 0;y < n-1;y++){
        System.out.print(finalNumber[y] + ", ");
    }

    currentNumber = 3; 
    int secondNumber[] = markOfMultiples(n, numbers, currentNumber);
    for(int y = 0;y < n-1;y++){
        System.out.println(secondNumber[y]);
    }

}

public static int[] markOfMultiples(int n, int numbers[], int currentNumber){

    int originalNumber = currentNumber;
    while(currentNumber<n){
        currentNumber = currentNumber + originalNumber;
        int count2 = 0;
        while(currentNumber != numbers[count2] && currentNumber<=n && count2<n){            
            count2++;
        }
        numbers[count2] = 0;
    }
    return numbers;
}

我得到的错误是:线程“main”中的异常 java.lang.ArrayIndexOutOfBoundsException: 20

在 sieveOfEratosthenes.sieveOfEratosthenes.markOfMultiples(sieveOfEratosthenes.java:46)

在 sieveOfEratosthenes.sieveOfEratosthenes.main(sieveOfEratosthenes.java:28)

第 28 行是我记忆函数的时候:int secondNumber[] = markOfMultiples(n, numbers, currentNumber);

第 46 行是 while(currentNumber != numbers[count2] && currentNumber<=n && count2<20){

任何帮助将不胜感激。如何继续调用该函数？

附注请原谅变量名，因为我会在程序运行时更改它们。

Answer 1

如果你想让这种方法起作用，你可以按照@Thierry 的建议进行修复以检查 count2 < n首先在你的 while 循环中，然后也环绕这条线

numbers[count2] = 0

使用 if 子句来检查 count2 是否超出索引的末尾。例如

if (count2 < n) {
    numbers[count2] = 0;
}

您的最后一个挑战是如何称呼您的 markOfMultiples()当 n 变大时，函数足够多次。这不是您的基本方法的问题 - 您绝对可以做到，并且您的方法会很好地工作并且对于低数(比如高达 10000)具有可接受的性能。

然而

我知道这是一项任务，您想按照自己的方式去做，但是您可能需要考虑您的方法的一些特征 - 也许在您开始工作之后。

1. 可读性 - 查看(标记)您的代码的人是否容易理解它在做什么并验证它是否会为所有 n 值做正确的事情？

2. 尽量不要重复你自己 - 例如考虑你在哪里填写你的 numbers数组:

   while(newNumber <= n){
      numbers[x] = newNumber;
      x++;
      newNumber++;
   }
   

   威尔x永远不同于newNumber ？你需要这两个变量吗？这种排序或重复发生在您代码的其他地方 - 要坚持的原则称为 DRY (Don't Repeat Yourself)

3. 有没有更简单的方法来移动 originalNumber 上的索引？在你的地方 markOfMultiples()方法？ (提示:是的，有)

4. 您真的需要 numbers[] 数组中的实际数字吗？如果你想出如何为 n 的高值重复调用 markOfMultiples，你将得到很多零和素数作为整数值。如果您使用数组索引为您提供素数，那么 1 和 0(或 true 和 false )的数组是否足够？