Using a step size of two will make it roughly twice as fast. Some
other comments:
You only need to sieve out multiples of primes. Your algorithm will do
redundant work for odd composite numbers like 9 and 15. You know that
all multiples of 9 were eliminated when you sieved out multiples of 3,
so you don't need to do it again.
Also, instead of doing all of the dividing and multiplying by two, you
could just define the bits to only represent the odd numbers. That way
you not only run faster, but you also use half the memory.
The method I described above essentially does this not only for 2, but
also for 3, 5, and 7. The runtime is roughly 48/210 as much as a full
sieve, but it also uses only 48 bits for a range of 210 numbers. This
means that you can sieve a larger range in whatever memory limit you
are working with.
Don
On Dec 20, 1:09 am, atul anand <atul.87fri...@gmail.com> wrote:
> i had implemented Sieve of Eratosthenes long time back...
> what i did was the following :-
> say N is the range and we want to find all prime number within this range.
> take size of temp array[] to half = N/2...as we only care of odd
> numbers.Prime number 2 can be handled explicitly.
> run outer loop for
> for(i=3 ; i<(sqrt(N))/2;i=i+2) // consider only odd "i"
> {
> for(j=i^2; (j/2)< N/2 ; j+= i*2) // here I am excluding even multiple
> of "j" by incrementing it by 2*i
> set(j,false);
>
> }
>
> when i ran this algo for N=2000000 , it took 45.302 ms
>
>
>
>
>
>
>
> On Sat, Dec 8, 2012 at 2:44 AM, Don <dondod...@gmail.com> wrote:
> > I know that the Sieve of Eratosthenes is a fast way to find all prime
> > numbers in a given range.
> > I noticed that one implementation of a sieve spends a lot of time
> > marking multiples of small primes as composite. For example, it takes
> > 1000 times as long to mark off all of the multiples of five as it
> > takes to mark off the multiples of 5003. In addition, when it is
> > marking off the multiples of larger primes, most of them are multiples
> > of small primes. In fact, if it could skip over multiples of 2,3,5,7,
> > and 11, the sieve would be about 5 times faster.
>
> > Can someone describe a way to make a sieve faster by not having to
> > deal with multiples of the first few prime numbers?
>
> > Don
>
> > --
--
