Not only even numbers, but you can extend the algorithm for other numbers as well.
Start with 2, mark all the numbers which are multiples of 2, then in the next iteration, take 3, and mark all the numbers which are multiples of 3. If a number is already marked, you dont consider that number in the consequent iterations, in our case, you skip marking the numbers which are multiples of 4, since 4 is already marked, all the multiples of 4 will also be marked. Ex: to find all the prime numbers till 20. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 0 < Iteration <= n/2 first iteration for 2, mark: 4,6,8,10,12,14,16,18,20 2nd iteration for 3, mark: 6,9,12,15,18 3rd iteration for 4, skip this iteration, since 4 is already marked, 4th iteration for 5, mark: 10, 15, 20 5th iteration for 6, skip 6th iteration for 7, mark: 14 7th iteration for 8, skip 8th iteration for 9, skip 9th iteration for 10, skip remaining numbers are prime numbers. On Sun, Apr 11, 2010 at 10:24 AM, Rohit Saraf <rohit.kumar.sa...@gmail.com>wrote: > why don't you remove all even numbers from consideration and add 2 > explicitly. I think that would help. > > > -------------------------------------------------- > Rohit Saraf > Second Year Undergraduate, > Dept. of Computer Science and Engineering > IIT Bombay > http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> > > > > On Sun, Apr 11, 2010 at 2:38 AM, Black Diamond <patidarc...@gmail.com>wrote: > >> i have an problem on SPOJ to find all the prime less than 10^8 >> https://www.spoj.pl/problems/TDPRIMES/ >> >> i am using sieve of erastosthenes algorithm to find primes >> my code is taking in my machine around 10.9 to 11.2 seconds >> and time limit is 10 second how i can change my code or any diff >> logic..??? >> //---------------------------------------------// >> #include<cstdio> >> using namespace std; >> #define ten8 (100000000) >> bool M[ten8]; >> int main() >> { >> int half=10000, i,j,x=0; >> for ( i = 0;i < ten8;i++) >> M[i] = false; >> for ( i = 2;i < ten8;i++) >> { >> if (M[i] == false) >> { >> x++; >> if(x%100==1) >> printf("%d\n",i); >> if(i>half) >> continue; >> >> for (int j = i * i;j < ten8;j += i) >> { >> M[j] = true; >> } >> } >> } >> } >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Thanks & Regards, - NMN -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.
<<My+Sign.JPG>>
