java - 质数算法不起作用

Question

package coding;
public class Prob7 {
public static void main(String[] args) {
    long flag=0;
    long counter=0;
    long prime;
    for(prime=2;;prime++){
        System.out.println(counter);
        flag=0;
        long check=2;
        while(check<=prime/2){
            if(prime%check==0){
                flag=1;
                break;
            }
        }
        if(flag==0){
            if(counter==10001){
                System.out.println(prime);
                break;
            }
            counter++;
        }

    }


  }

}

我想找到第 10001 个质数，我在 for 循环中嵌套了一个 while 循环，用于查找它是否是质数。我使用标志检查循环外部，并在必要时跳出 while 循环。但是控制台什么也没做。所以在 for 循环的下一行，我放置了 System.out.println(counter); 来检查发生了什么。计数器打印出来

0
1
2
2

然后停下来。我试过调试，但我无法找出问题所在。我没有为 for 循环设置条件，因为我有一个 break 语句，如果素数计数器达到 10001，该语句将跳出循环。

PS:我知道我可以使用 isPrime()，但我只想练习这些算法。

Answer 1

您不会在内部 while 循环中递增 check 变量。修改为:

    while(check<=prime/2){
        if(prime%check==0){
            flag=1;
            break;
        }
        ++check;
    }

一般而言，如何改进算法有很多方法:

1. 您可以在开始时测试 2，然后只检查奇数(所以 check += 2)
2. 您可以在开始时计算 sqrt(prime)，然后只循环直到平方根(因为 (sqrt(x)+1)^2 将始终高于素数)。
3. 您可以考虑完全不同的算法，记住已经成功测试的素数，并且在测试另一个素数测试时已经发现素数仅作为除数。这类似于 Sieve of Eratosthenes .