java - 使用埃拉托色尼筛法寻找第 n 个素数

Question

我正在使用 Eratosthenes 的 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 个的素数。