使用埃拉托斯特尼筛法查找第n个质数

Question

我正在使用埃拉托斯特尼筛法来计算第1,000,001个质数，但是我无法计算使用筛法的上界。我的函数：

public static void Seive(int num){
    BitSet primes = new BitSet();

    for(int i=2; i<=num; i++){
        if(!primes.get(i)){
            for(int j=i+i; j<=num; j+=i){
                primes.set(j);
            }
        }
    }

    for(int i=2; i<=num; i++){
        if(!primes.get(i))
            System.out.print(i + " ");
    }       

}

计算从2到num的质数，但如果我不知道范围，而是想找到第n个数字呢。

- Mayur Kulkarni

---

只是一条提示，你可以观看Numberphile在Youtube上关于质数的视频，“第n个质数约等于n×ln(n)”。 - Arc676

https://www.maa.org/sites/default/files/jaroma03200545640.pdf - Sergey Kalinichenko

只是一个小细节，但如果您将 i+i 替换为 i*i，筛法代码将运行得更快。 （所有小于 i*i 的合数已经从筛子中消除了，因此没有必要再次访问它们。） - r3mainer

可能是如何使用埃拉托色尼筛法获取第n个质数？的重复问题。 - Erick G. Hagstrom

Answer 1

一个与素数定理相关的推论表明，对于大于5的自然数n，第n个素数介于nlogn和n(logn+loglogn)之间，其中的对数都是以自然对数e为底。因此，找到前n个素数的一个简单方法是筛选出不超过上限的所有素数，然后丢弃第n个素数之后的素数。

- user448810

Answer 2

这是欧拉计划-问题7中我怀疑你正在处理的关键点。它被设计成使得使用筛法很困难。这个问题足够小，可以使用暴力方法，或者存储质数并使用它们进行暴力计算，而不是标准的暴力除法。

- Ross Drew

---

PE7 的目标是寻找第 10,001 个质数，而我的目标是寻找第 1,000,001 个质数 :-D - Mayur Kulkarni

使用基于上限的算法很难，因为所需的上限未知。 - Ross Drew

存储质数需要知道上限，那么我怎么知道质数列表已经完成，以便我可以进行暴力计算？ - Mayur Kulkarni

是的，您要查找的质数数量不是未知的上限。前几个可以硬编码或生成。每次使用质数来计算下一个时，将其添加到列表中并从那时起使用它。 - Ross Drew

Answer 3

请查看质数定理。一个好的上界近似值为n * ln(n)（这里底数有影响）。

- Ivaylo Strandjev