The Sieve of Eratosthenes is best for finding prime
On Mon, Apr 12, 2010 at 10:58 AM, BlackdiamonD <patidarc...@gmail.com>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
> <karthik.gin...@gmail.com>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 <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.
>>>
>>
>>
>>
>> --
>> 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 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.
>>
>
>
>
> --
> ~~~~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 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.
>
--
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 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>>
