使用埃拉托色尼筛法寻找第 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

这就是 Project Euler - Problem 7 that I suspect your working on. It's designed in such a way as to make it hard to use the sieve 中的重点。这个问题足够小，可以使用 brute force method 或代替标准的强力除法，存储你的质数和使用它们的强力。

Answer 2

看看prime number theorem。上限的一个很好的近似值是 n * ln(n)（这里底数确实很重要）。

Answer 3

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

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

Finding nth prime using Seive of Eratosthens

java

algorithm

math

primes