Ah, sieving. This is a stroll down memory lane for me, as nearly 10 months ago, the Sieve of Eratosthenes was the first algorithm I had to learn myself, while attempting to solve a question on SPOJ. But anyways, let’s jump right in.

So! Sieving!

I discovered this approach on a question, and here’s that question -

Given N queries, each containing a single integer X, determine if the given X, is a prime number or not. If X is prime, print “yes” else print “no”.

Now, of course, the question is simple to brute force. The brute force complexity would be O(Nmax(X)), or with some pruning and observation-based optimizations, one could speed it up to O(N√(max(X))), but that wasn’t enough. In fact, that was my first solution which, upon showing me a “Time Limit Exceeded” verdict, forced me to resort to reference websites.

Well, the short answer to how you solve the above question optimally, is sieving.

Here’s the core principle behind the algorithm -

Given a number x (either prime or composite) > 1, we know all it’s multiples of the form k*x CANNOT be prime. i.e,

∀ x,k ∈ ℕ: k*x ∉ P (where P is the set of all primes)

Thus, here’s the way it works in code -

bool isprime[N]; //Define a hash map isprime[i] to state if i is prime or not
for(int i=0;i<N;i++)
     isprime[i]=1; //Assert the case all numbers are prime for now
isprime[0]=0;
isprime[1]=0;  //Handle base cases
for(int i=2;i<=sqrt(N);i++)
     if(isprime[i]) //If the current number is a prime, proceed
          for(int j=i*i;j<N;j+=i)
               isprime[j]=0; //mark all multiples of i as composite

//That's it! isprime[i] tells us the primality of i now in O(1)!

And that’s how a simple prime generator is implemented in the form of a sieve. Now, its possible to check if a number is prime in O(1).

It’s worth mentioning that the average complexity of this algorithm is O(N * logN) (More specifically, it’s O(N * logN * loglogN) but that last term doesn’t matter all that much in practice)

So that’s how primality is dealt with, sieve-style! Now let’s look at it under different lights.

Sieving is a concept easy to understand but hard to master, every now and then, I still manage to come across a problem where upon reading the editorial, I raise an eyebrow going “Wut, sieving here? Man.”

A few nice questions on sieving are as follows -

SPOJ - PRIME1

The straight-forward question that asks you to literally apply what you just read above, this one should be a good indicator of how well you picked up this concept.

CodeChef - KPRIME

In this question, the tl:dr; version of the algorithm is as follows - generate all primes using the above sieving technique into a boolean array isPrime.

After doing this, use a similar sieving algorithm on another array numberOfPrimeFactors, i.e. for every number that is a prime, add 1 to all its multiples for it contributes to them as a prime factor.

And that’s all, an AC awaits you.

In addition, it’s also useful in finding, say, the smallest prime factor of a given number. Consider the following implementation -

bool isprime[N];
int len, smallest[N];
isprime[0]=isprime[1]=0;
for(int i=2;i<N;i+=2){ 
     isprime[i]=1;
     smallest[i]=2; //the smallest prime factor of even numbers is 2
}
for(int i=3;i<N;i+=2){ 
     if(isprime[i]){ //if the number is prime
          smallest[i] = i; //set it to itself
          for(int j=i;(j*i)<N;j+=2){  //iterate over its odd multiples       
               if (isprime[j*i]) //if it is prime, reset it, and update smallest prime factor
                    isprime[j*i] = false, smallest[j*i] = i; 
          } 
     }
}

Of course, there are other ways to determine the primality of a number (Fermat’s Little Theorem, Miller-Rabin Algorithm, or the smallest factors of a number, but sieves accomplish them well enough too and are easy to implement quickly.

There’s also an O(N) implementation of a prime sieve, and that’s published in an ACM journal. Here’s the link to the research paper - http://www.cs.utexas.edu/users/misra/scannedPdf.dir/linearSieve.pdf

And that’s the basics of sieving!

Good luck applying it!

Aditya