10394 - Twin Primes
Moderator: Board moderators
-
- 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?
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?
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).
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));
-
- Learning poster
- Posts: 67
- Joined: Sun Sep 22, 2002 5:40 am
- Location: Taiwan
-
- New poster
- Posts: 28
- Joined: Wed Jul 31, 2002 10:33 am
- Location: Ukraine
- Contact:
-
- Guru
- Posts: 647
- Joined: Wed Jun 26, 2002 10:12 pm
- Location: Hong Kong and New York City
- Contact:
But how do you derive such a thing?
#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:
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...
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...
-
- New poster
- Posts: 28
- Joined: Wed Jul 31, 2002 10:33 am
- Location: Ukraine
- Contact:
Once again, why is it
in the original sieve algorithm?
It is correct to write
And it is possible to modify sieve algorithm so it will not delete one number more than one time (will be linear)
for(int j=i*2;j<MAX;j+=i) isprime[j]=0;
in the original sieve algorithm?
It is correct to write
because if x=a*b (a,b>=2), then x will be deleted (isprime[x]=0) when i=min(a,b).for(int j=i*i;j<MAX;j+=i) isprime[j]=0;
And it is possible to modify sieve algorithm so it will not delete one number more than one time (will be linear)
-
- 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);
}
#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);
}
I have two questions: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));
1.
Why the size of char a[] is MAXSIEVE/16+2, not MAXSIEVE/8 ?char a[MAXSIEVE/16+2]
2.
Why the loop condition is j<MAXSIEVEHALF, not j<MAXSIEVEfor(j=i+i+i+1;j<MAXSIEVEHALF;j+=i+i+1)
Please tell me, thanx.
-
- New poster
- Posts: 28
- Joined: Wed Jul 31, 2002 10:33 am
- Location: Ukraine
- Contact: