Page **1** of **7**

### 10394 - Twin Primes

Posted: **Tue Nov 05, 2002 4:19 pm**

by **Ghost77 dimen**

Is my method to calculate the prime is too slow???

Why still someone can

**"far"** faster than mine?I spend about 1 second.

But the fastest one only use 0.1 second.Can anyone help me out?

Posted: **Wed Nov 06, 2002 4:49 am**

by **Yarin**

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).

Posted: **Fri Nov 08, 2002 2:48 am**

by **amd-RS**

What's the algorithm did you use for calculating primes ???

Thanks in advance !!

Posted: **Fri Nov 08, 2002 6:27 am**

by **Yarin**

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));

Posted: **Fri Nov 08, 2002 10:10 am**

by **Ghost77 dimen**

Hi , amd-RS.

My method is like what Yarin said.

But it is a coincide that the memory is enough.

It doesn't work always , thinking for a while before using it.

Good luck.

Posted: **Mon Nov 11, 2002 2:10 pm**

by **Larry**

But where did you guys come up with that?

Posted: **Tue Nov 12, 2002 11:46 am**

by **Alexander Grushetsky**

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:

for(j=i+i+i+1;j<MAXSIEVEHALF;j+=i+i+1)

you can write

for(j=2*i*(i+1);j<MAXSIEVEHALF;j+=i+i+1)

and receive the same result but some faster.

Posted: **Thu Nov 14, 2002 7:46 pm**

by **Larry**

#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));

But how do you derive such a thing?

Posted: **Thu Nov 14, 2002 8:07 pm**

by **Yarin**

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...

Posted: **Thu Nov 14, 2002 10:18 pm**

by **Alexander Grushetsky**

Once again, why is it

for(int j=i*2;j<MAX;j+=i) isprime[j]=0;

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)

Posted: **Fri Nov 15, 2002 2:12 am**

by **Yarin**

Ohhh... I guess I've never thought about that. Thanks

### Method for generating prime faster

Posted: **Sun Nov 17, 2002 9:57 am**

by **Jewel**

#include<stdlib.h>

#include<malloc.h>

#define isprime(f,x) (*(f+(x)/16)&(1<<(((x)%16L)/2)))

#define setprime(f,x) *(f+(x)/16)|=1<<(((x)%16L)/2)

void main()

{

unsigned char *field=NULL,*zzz;

unsigned long teste=1,max,mom,count,alloc;

max=20010000L;

while(field==NULL)

zzz=field=(unsigned char*) malloc(alloc=(((max-=10000L)>>4)+1L));

for (count=0;count<alloc;count++)

*zzz++ = 0x00;

while((teste+=2)<max)

if(!isprime(field,teste))

for(mom=3L*teste;mom<max;mom+=teste<<1)

setprime(field,mom);

/*now you can cll the module isprime to check any positive integer

either prime or not;

syntax:

isprime(field,integer);

if the module return 0 the integer will be prime

else not prime.

you can check upto 20000000 within a while

*/

free (field);

}

Posted: **Tue Dec 24, 2002 10:57 am**

by **deddy one**

Posted: **Mon Jan 06, 2003 12:01 pm**

by **eloha**

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

Please tell me, thanx.

Posted: **Mon Jan 06, 2003 10:45 pm**

by **Alexander Grushetsky**

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.