Try taking the sqrt(N) outside the for loop. I believe it is
executing every time the condition is being checked. That should do.
On Thu, Dec 20, 2012 at 12:09 PM, 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
>>
>> --
>>
>>
>>
> --
>
>
>
--
