Re: [algogeeks] Sieve
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.comwrote:
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=200 , 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
--
--
--
Re: [algogeeks] array problem
It will be even easier with BIT (Binary Indexed Tree), if you know how to use it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] question
Convert the integer to a binary string. From the right (that is least significant bit), find the first occurence of 01 in the string. For example.. if the string is *00110 **01 **11100*, notice the isolated part, that is what you have to find. Then simply flip the 01 to 10.. like *00110* *10**11100.* And then move all the 1's that you skipped to the right.. like *00110**10**00111* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] JAVA PROGRAM ERROR
it should be x - 1 not n - 1 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: MS Question : find word in 2D array
This can be done with a dfs to mark the path and a backtrack to construct the path or the word itself. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
