使用 Seive of Eratosthens 寻找第 n 个素数

Question

我正在使用埃拉托色尼的 Seive 来计算第 1,000,001 个素数，但是，我无法计算使用 Seive 的上限。我的功能：

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 个数字怎么办。

Answer 1

素数定理的一个推论指出，对于n > 5，第n个素数介于n log n和n (log n + log log n ) 之间，以e为底的对数。因此，找到前n 个素数的一种简单方法是筛选到上限，然后丢弃超出第n个的素数。