哪种埃拉托色尼筛法实施更有效？

Question

我有两个埃拉托色尼筛法的实现。这是第一个：

public class SieveOfEratosthenes extends PrimeGenerator {

    private boolean[] sieve;
    private List<Integer> primes;

    public SieveOfEratosthenes(int depth) {
        super(depth);

        sieve = new boolean[depth + 1];
        primes = new ArrayList<>();

        generate();
    }

    private void setPrime(int n) {
        sieve[n] = true;
        primes.add(n);
    }

    private void generate() {
        setPrime(2);
        setPrime(3);

        for (int n = 4; n <= depth; n++) {
            boolean isPrime = true;

            for (int prime : primes) 
                if (n % prime == 0) 
                    isPrime = false;

            if (isPrime)
                setPrime(n);
        }
    }
}

这是第二个。

public boolean[] sieve(int n)
{
   boolean[] prime=new boolean[n+1];
   Arrays.fill(prime,true);
   prime[0]=false;
   prime[1]=false;
   int m=Math.sqrt(n);

   for (int i=2; i<=m; i++)
      if (prime[i])
         for (int k=i*i; k<=n; k+=i)
            prime[k]=false;

   return prime;
}

显然第二个不那么冗长。它并不意味着成为素数生成器层次结构的一部分。但我的问题是，哪个更有效率？第一个似乎是 O(N*log(N)) 但我不确定。我不确定第二个的增长率是多少。

Answer 1

第二种效率更高。它也是埃拉托色尼筛法。第一种算法是试分法，不是埃拉托色尼筛法

第一个算法的时间复杂度为 O(n sqrt(n))，或者如果你使用只有质数作为试验除数。第二种算法的时间复杂度为 O(n log log n)，这几乎是线性的，因为 log log n 很小.

作为实验，计算前百万个素数，最多 15485863 个，看看哪个更快。它甚至不会接近。第二种算法将在几秒钟内完成。第一个算法需要几个小时。

哪种埃拉托色尼筛法实施更有效？

Which Sieve of Eratosthenes implementation is more efficient?

java

algorithm

big-o