## 10394 - Twin Primes

Moderator: Board moderators

Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

### 10394 - Twin Primes

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?
Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
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).
amd-RS
New poster
Posts: 27
Joined: Thu Sep 05, 2002 7:37 am
What's the algorithm did you use for calculating primes ???

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
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));
Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan
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.
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
But where did you guys come up with that?
Alexander Grushetsky
New poster
Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine
Contact:
There are many ways to get better time without using inline-assembler and hard optimization, but with using some better algorithm.
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.
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

#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?
Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
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...
Alexander Grushetsky
New poster
Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine
Contact:
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)
Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
Ohhh... I guess I've never thought about that. Thanks
Jewel
New poster
Posts: 1
Joined: Thu Jul 11, 2002 1:49 pm
Location: The University of Asia Pacific Bangladesh

### Method for generating prime faster

#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);
}
deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm
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

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan
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