thankx for u r reply.in my code i implemented Sieve of Eratosthenesthat but some type of optimization were required that i have done...got accepted.
On Wed, Apr 14, 2010 at 2:57 PM, Ashish Mishra <[email protected]>wrote: > The Sieve of Eratosthenes is best for finding prime > > > On Mon, Apr 12, 2010 at 10:58 AM, BlackdiamonD <[email protected]>wrote: > >> thank kartik thanks but it was with lot of optimized code i was unable to >> understand though i have changed my code more know it is taking around 8 to >> 8.5 seconds in my computer but still i am getting TLE on server >> >> #include<stdio.h> >> #define ten8 (100000000) >> const int mod=32; >> unsigned int M[ten8/mod]; >> int main() >> { >> int half=10000, i,j,x=1; >> int y=ten8/mod; >> freopen("output.txt","wt",stdout); >> for ( i = 0;i < y;i++) >> M[i] = 0; >> printf("2\n"); >> for ( i = 3;i < ten8;i+=2) >> { >> int a=i/mod,b=i%mod; >> if (((M[a]>>b)&1)==0) >> { >> x++; >> if(x%100==1) >> printf("%d\n",i); >> if(i>half) >> continue; >> for (int j = i * i;j < ten8;j += i) >> { >> M[j/mod] =M[j/mod]|(1<<(j%mod)); >> } >> } >> } >> } >> >> On Sun, Apr 11, 2010 at 7:20 AM, Karthik Reddy >> <[email protected]>wrote: >> >>> http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html >>> >>> take a look at this link . The running time is less than 2 sec for 10^8. >>> >>> On Sun, Apr 11, 2010 at 2:38 AM, Black Diamond <[email protected]>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 [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]<algogeeks%[email protected]> >>>> . >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>> >>> >>> >>> -- >>> Ram Karthik Reddy Ginuga >>> karthik.ginuga[at]gmail.com >>> CCNA,MCP >>> Mozilla Campus Ambassador >>> SPOJ world rank #1088 >>> http://www.spoj.pl/users/karthu/ >>> (91)40 27425999 >>> (91)9247818845 >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]<algogeeks%[email protected]> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> ~~~~BL/\CK_D!AMOND~~~~~~~~ >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > Ashish Mishra > http://ashishmishra.weebly.com/ > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- ~~~~BL/\CK_D!AMOND~~~~~~~~ -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
<<My+Sign.JPG>>
