Optimized Sieve of Eratosthenes

Sieve of Eratosthenes is a very good and famous method for finding a large number of primes. It is based on a general idea to flag out those numbers which are composite, and thus the numbers which remain are prime.

However, it can be optimized and there are a number of ways to do it.
There are many problems on Spoj, UVa that can be solved using sieve method.
One can extend general notion of sieve to solve other problems related to ETF, LCM, GCD, divisor summation etc.



Here is my code for it :-





The idea behind optimization is to leave those numbers which are divisible by 2 and 3.
It makes the sieve 3 times faster.


Here are some problems that can be tried with optimized sieve:

PRIME1
FINDPRM
CPRIME
TDKPRIME
TDPRIMES