java - 计算第 10001 个素数

Question

我想像问题7 euler project 一样计算第 10001 个素数。这就是我所做的：

int i=0;
int counter=2;
while (i<=10001){
    counter++;
    if (Helper.isPrime(counter))
        i++;
}
Helper.println(counter);

它正在返回104033，但正确答案是104743。我的问题在哪里？

Answer 1

您的代码存在三个问题：

1. 您的代码没有测试 2 是否是素数，因此您在计数中缺少它。您应该初始化counter为 0 或 1，而不是 2。
2. 通过使用while (i<=10001)，您将一直数到找到 10002 个素数。由于您也没有数 2，因此您将超过您需要去的地方两步。循环测试应该是while (i<10001).
3. 由于您的答案低于正确答案（即使您的循环超过了应该停止的两个素数），您的Helper.isPrime方法显然将太多数字标识为素数。它需要修复，但由于您尚未发布它的代码，因此无法说出修复它需要什么。

Answer 2

正确版本

int i=0;
int counter=1; // chnage initial value of counter
while (i<10001){ // change terminating condition
    counter++;
    if (Helper.isPrime(counter))
        i++;
}
Helper.println(counter);

您的版本的说明/问题

首先解决较小的子集，假设您要打印第三个素数。根据您的代码

i=0, counter  =3, is 3 prime yes i=1
i=1  counter = 4 is 4 prime No i =1
i=1 counter = 5 is 5 prime Yes i=2
i=2 counter =6 is 6 prime No i=2
i=2 counter =7 is 7 prime yes i=3
i=3 counter =8 is 8 prime no i=3
i=3 counter = 9 is 9 prime no i=3
i=3 counter =10 is 10 prime no i=3
i=3 counter =11 is 11 prime yes i=4
loop terminates
ans: 11

是 11 的第二素数，否

问题：

1. 为什么计数器以 2 开头
2. 循环的终止条件，即使找到数字，我们也不会终止

Answer 3

尝试

   int find=10001;
   int counter =1;
   int currentNumber=2;
   while (counter <= find){
       if(Helper.isPrime(currentNumber)){
           counter++;              
       }
       currentNumber++;
   }
    System.out.println(currentNumber-1);