如何回忆一个函数,Eratosthenes 筛法
How to recall a function, Sieve of Eratosthenes
我正在尝试编写代码,使用埃拉托色尼筛法计算出素数。我必须包含一个函数,该函数将接受一个数字和该数字的所有倍数的交叉。为了测试,我将第一个数字设置为 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){
如有任何帮助,我们将不胜感激。如何继续调用函数?
p.s。请原谅变量名,因为我会在程序运行时更改它们。
您需要在访问数字之前测试 count2 < n 是否[count2]:
while(count2 < n && currentNumber != numbers[count2] && currentNumber<= n){
count2++;
}
如果你想让这种方法起作用,你可以按照@Thierry 的建议进行修复,首先在你的 while 循环中检查 count2 < n
,然后也包围行
numbers[count2] = 0
使用 if 子句检查 count2 是否超出索引末尾。例如
if (count2 < n) {
numbers[count2] = 0;
}
您的最后一个挑战是当 n 变大时如何足够多次调用 markOfMultiples()
函数。这不是你的基本方法的问题 - 你绝对可以做到,你的方法会很好地工作并且对于低数(比如高达 10000)具有可接受的性能。
然而
我知道这是一项任务,您想按照自己的方式去做,但是您可能需要考虑您的方法的一些特征 - 也许在您完成它之后。
- 可读性 - 查看(标记)您的代码的人是否容易理解它在做什么并验证它是否会为 n 的所有值做正确的事情?
尽量不要重复你自己 - 例如考虑你在哪里填充你的 numbers
数组:
while(newNumber <= n){
numbers[x] = newNumber;
x++;
newNumber++;
}
x
会与 newNumber
不同吗?你需要这两个变量吗?这种排序或重复发生在代码的其他地方——要坚持的原则被称为 DRY (Don't Repeat Yourself)
在您的 markOfMultiples()
方法中,是否有更简单的方法将索引移动到 originalNumber
位置? (提示:是的,有)
您真的需要 numbers[] 数组中的实际数字吗?如果你想出如何为 n 的高值重复调用 markOfMultiples,你将得到很多零和素数作为整数值。如果你使用数组索引给你素数,一个 1 和 0(或 true
s 和 false
s)的数组是否足够?
我正在尝试编写代码,使用埃拉托色尼筛法计算出素数。我必须包含一个函数,该函数将接受一个数字和该数字的所有倍数的交叉。为了测试,我将第一个数字设置为 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){
如有任何帮助,我们将不胜感激。如何继续调用函数?
p.s。请原谅变量名,因为我会在程序运行时更改它们。
您需要在访问数字之前测试 count2 < n 是否[count2]:
while(count2 < n && currentNumber != numbers[count2] && currentNumber<= n){
count2++;
}
如果你想让这种方法起作用,你可以按照@Thierry 的建议进行修复,首先在你的 while 循环中检查 count2 < n
,然后也包围行
numbers[count2] = 0
使用 if 子句检查 count2 是否超出索引末尾。例如
if (count2 < n) {
numbers[count2] = 0;
}
您的最后一个挑战是当 n 变大时如何足够多次调用 markOfMultiples()
函数。这不是你的基本方法的问题 - 你绝对可以做到,你的方法会很好地工作并且对于低数(比如高达 10000)具有可接受的性能。
然而
我知道这是一项任务,您想按照自己的方式去做,但是您可能需要考虑您的方法的一些特征 - 也许在您完成它之后。
- 可读性 - 查看(标记)您的代码的人是否容易理解它在做什么并验证它是否会为 n 的所有值做正确的事情?
尽量不要重复你自己 - 例如考虑你在哪里填充你的
numbers
数组:while(newNumber <= n){ numbers[x] = newNumber; x++; newNumber++; }
x
会与newNumber
不同吗?你需要这两个变量吗?这种排序或重复发生在代码的其他地方——要坚持的原则被称为 DRY (Don't Repeat Yourself)在您的
markOfMultiples()
方法中,是否有更简单的方法将索引移动到originalNumber
位置? (提示:是的,有)您真的需要 numbers[] 数组中的实际数字吗?如果你想出如何为 n 的高值重复调用 markOfMultiples,你将得到很多零和素数作为整数值。如果你使用数组索引给你素数,一个 1 和 0(或
true
s 和false
s)的数组是否足够?