I wouldn't care too much about the low execution times some people get on some problems. In most cases this is either due some really crazy optimizations (like using inline assembly and tweaking input/output) or really big precalculated lookup tables. There are some people who seem to take a big delight in doing these kind of optimizations just to be #1 on the ranklists, which kind of removes it's purpose (partially).
#define MAXSIEVE 100000000 // All prime numbers up to this
#define MAXSIEVEHALF (MAXSIEVE/2)
#define MAXSQRT 5000 // sqrt(MAXSIEVE)/2
char a[MAXSIEVE/16+2];
#define isprime(n) (a[(n)>>4]&(1<<(((n)>>1)&7))) // Works when n is odd
int i,j;
memset(a,255,sizeof(a));
a[0]=0xFE;
for(i=1;i<MAXSQRT;i++)
if (a[i>>3]&(1<<(i&7)))
for(j=i+i+i+1;j<MAXSIEVEHALF;j+=i+i+1)
a[j>>3]&=~(1<<(j&7));
There are many ways to get better time without using inline-assembler and hard optimization, but with using some better algorithm.
For example, instead of:
#define MAXSIEVE 100000000 // All prime numbers up to this
#define MAXSIEVEHALF (MAXSIEVE/2)
#define MAXSQRT 5000 // sqrt(MAXSIEVE)/2
char a[MAXSIEVE/16+2];
#define isprime(n) (a[(n)>>4]&(1<<(((n)>>1)&7))) // Works when n is odd
int i,j;
memset(a,255,sizeof(a));
a[0]=0xFE;
for(i=1;i<MAXSQRT;i++)
if (a[i>>3]&(1<<(i&7)))
for(j=i+i+i+1;j<MAXSIEVEHALF;j+=i+i+1)
a[j>>3]&=~(1<<(j&7));
You start with the original sieve algorithm, like this:
char isprime[MAX];
for(int i=0;i<MAX;i++) isprime=i>=2;
for(int i=2;i<MAX;i++)
if (isprime) // i is a prime, so make all multiples of it non-prime
for(int j=i*2;j<MAX;j+=i) isprime[j]=0;
Then you realize you can store the data more compact since isprime is really just a bit array. That introduces bitmasks. The final step is to only consider odd numbers, and make 2 a special case. When considering only odd numbers, you let index 1 be 3, index 2 be 5 etc. This causes the somewhat strange loops...
in the original sieve algorithm?
It is correct to write
for(int j=i*i;j<MAX;j+=i) isprime[j]=0;
because if x=a*b (a,b>=2), then x will be deleted (isprime[x]=0) when i=min(a,b).
And it is possible to modify sieve algorithm so it will not delete one number more than one time (will be linear)
it's quite shocking to see your guys algo here. umm, I definitely perhaps the dummiest guy posting in this thread, I mean, I know the original sieve algo , but what yarin do or jewel do here is totally awesome, I don't have a clue how did they get idea like that it's amazing
Yarin wrote:My memory-tight sieve looks like this:
#define MAXSIEVE 100000000 // All prime numbers up to this
#define MAXSIEVEHALF (MAXSIEVE/2)
#define MAXSQRT 5000 // sqrt(MAXSIEVE)/2
char a[MAXSIEVE/16+2];
#define isprime(n) (a[(n)>>4]&(1<<(((n)>>1)&7))) // Works when n is odd
int i,j;
memset(a,255,sizeof(a));
a[0]=0xFE;
for(i=1;i<MAXSQRT;i++)
if (a[i>>3]&(1<<(i&7)))
for(j=i+i+i+1;j<MAXSIEVEHALF;j+=i+i+1)
a[j>>3]&=~(1<<(j&7));
I have two questions:
1.
char a[MAXSIEVE/16+2]
Why the size of char a[] is MAXSIEVE/16+2, not MAXSIEVE/8 ?
2.
for(j=i+i+i+1;j<MAXSIEVEHALF;j+=i+i+1)
Why the loop condition is j<MAXSIEVEHALF, not j<MAXSIEVE
We can save memory and time if we don't take into account even numbers because all of them (except for 2) are not prime numbers. So we check primality only for odd numbers.