Hi, Black DiamonThere is a trick that number that can be devided by 2 or 3 is ignored, so we just deal with number 6n + 1 and 6n + 5, so you can try this:
#include<cstdio>
using namespace std;
#define ten8 (100000000)
bool M[ten8];
int main()
{
int half=10000, i,j,x=0;
int table = 4;
for ( i = 0;i < ten8;i++)
M[i] = false;
printf("2\n");
x = 2; // 2 and 3 are prime number;
for (i = 5;i < ten8;table = 6 - table, i += table) //only deal with 6n
+ 1 and 6n + 5
{
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;
}
}
}
}
On Sun, Apr 11, 2010 at 5:08 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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
<<My+Sign.JPG>>
