Hello
Below is a working code for the sieve .. it has the wheel 23 optimization i.,e all multiples of 2 and 3 are directly ignored (not stored at all). It generates primes upto 10^8 in around ~ 1.6s
Can any 1 suggest a few more optimizations ?
Can the bits(bit,bit1,bit2 in code) be toggled any faster ?
Thank you
Code:
#include <ctime>
#include <cmath>
#include <cstdio>
#include <algorithm>
#define MAX 100000000
using namespace std;
bool isprime[MAX/3];
void make_primes2()
{
int i,j,lim=sqrt(MAX);
bool bit1=1,bit2;
for(int i=5;i<=lim;i+=bit1?2:4,bit1=!bit1)
{
if(!isprime[i/3])
{
bit2=1;
for(int j=i;;)
{
j+=bit2?i<<2:i<<1;
bit2=!bit2;
if(j>=MAX)break;
isprime[j/3]=1;
}
}
}
}
int main()
{
make_primes2();
printf("%lf(s)\n",clock()/1e6);
return 0;
}