CODEWITHSUNDEEP
javaalgorithmbig-o
ktm5124
ktm5124

Reputation: 12123

Which Sieve of Eratosthenes implementation is more efficient?

I have two implementations of the Sieve of Eratosthenes. Here's the first:

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);
        }
    }
}

And here's the second.

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;
}

Obviously the second is less verbose. It's not meant to be part of a hierarchy of prime generators. But my question is, which is more efficient? The first one seems to be O(N*log(N)) but I am not sure of that. I'm not sure what the growth rate would be of the second.

Upvotes: 2

Views: 295

Answers (1)

user448810
user448810

Reputation: 17866

The second is more efficient. It is also the Sieve of Eratosthenes. The first algorithm is trial division, and is not the Sieve of Eratosthenes.

The first algorithm has a time complexity of O(n sqrt(n)), or perhaps a bit less if you use only primes as trial divisors. The second algorithm has a time complexity of O(n log log n), which is near-enough linear since log log n is very small.

As an experiment, compute the first million primes, up to 15485863, and see which one is faster. It won't be even close. The second algorithm will finish in a few seconds. The first algorithm will take a few hours.

Upvotes: 4

Related Questions