Eratosthenes的筛子故障

Question

我想在Java中创建一个Eratosthenes的筛子，但我写的代码似乎有缺陷。 我想知道是否有其他人可以发现我的错误，因为我不能。我得到的输出只是[2]，这意味着我的主循环不起作用。我只是刚开始使用Java，所以如果你能给出详细的答案，我将不胜感激。

我的代码：

public static int[] primes(int n) 
{ 
    //Variable assignement 
    double sqrt; 
    List<Integer> primes= new ArrayList<Integer>(); 
    //Adds 2 to primes so i don't need to include the even numbers in my for loop. 
    if(n>1) 
    { 
     primes.add(2); 
    } 
    //For loop that goes through the oneven numbers up to n 
    for(int counter1=3;counter1<=n;counter1+=2) 
    { 
     sqrt=Math.floor(Math.sqrt(0.0+counter1)); 
     //for loop that tests if the first for loops number is prime 
     for(int counter2=0;sqrt<=primes.get(counter2);counter2++) 
     { 
      if(counter1 % primes.get(counter2) != 0 && counter2 ==sqrt) 
      { 
       primes.add(counter1); 
      } 

      if(counter1 % primes.get(counter2)==0) 
      { 
       break; 
      } 
     } 
    } 
    return convertIntegers(primes); 
} 
//Converts the list to an array 
public static int[] convertIntegers(List<Integer> integers) 
{ 
    int[] ret = new int[integers.size()]; 
    for (int i=0; i < ret.length; i++) 
    { 
     ret[i] = integers.get(i).intValue(); 
    } 
    return ret; 
} 

Answer 1

我没有彻底检查您的代码，但可能存在精确问题。 请注意，double可能不会精确地表示整数值，因此counter2 ==sqrt可能是错误的，即使sqrt似乎是整数。

为了防止这种情况，尝试以下方法：

//this is not necessarily a square root anymore, btw :) 
int sqrt = (int) Math.floor(Math.sqrt((double)counter1)); 
... 
for(...) { 
    ... 
    if(... && counter2 ==sqrt) { 
    ... 
    } 
    ... 
} 

编辑：稍微经过分析收率

甲此：

假设N = 5，因此，下面的步骤将是在您的代码中执行：

1. counter1 = 3
2. sqrt = 1 //地板（SQRT（2））
3. counter2 = 0
4. counter1 % primes.get(counter2) != 0 && counter2 ==sqrt是假，因为3 % 2 = 1 BUT 0 != 1
5. counter1 % primes.get(counter2)==0是假，因为3 % 2 = 1
6. counter2 = 1（下一次迭代）
7. primes.get(counter2)引发例外，因为primes.get(1)需要primes有至少2个元素。

你可能会尝试的是counter2 <=sqrt。

Answer 2

if(counter1 % primes.get(counter2)==0);{ 
    break;} 
} 

是不太可能有帮助的事项。在大括号之前你有一个分号 - 你的休息总是会被执行。