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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
<<My+Sign.JPG>>
