10394 - Twin Primes

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
Yu Fan
New poster
Posts: 26
Joined: Thu Nov 13, 2003 3:52 am

10394 Output Limit Execeed

Post by Yu Fan » Wed Mar 24, 2004 12:41 pm

I don't know what wrong with my code,please tell me~

#include <stdio.h>
int main() {
int p[607],i=3,j=1,k,ans[100000]={-1},n,m,x;
p[0]=2;
while(i<4482) {
for(k=0;p[k]*p[k]<i;k++)
if(i%p[k]==0) break;
if(p[k]*p[k]>i)
p[j++]=i;
i+=2;
}
j=2;
ans[0]=3;
ans[1]=5;
while(scanf("%d",&n)) {
if(n<j);
else {
i=j;
m=ans[j-1]+6;
x=m+2;
while(j<n) {
for(k=0;p[k]*p[k]<x;k++)
if(m%p[k]==0||x%p[k]==0) break;
if(p[k]*p[k]>x)
ans[j++]=m;
m+=6;
x+=6;
}
}
printf("(%d, %d)\n",ans[n-1],ans[n-1]+2);
}
return 0;
}

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Thu Mar 25, 2004 7:33 am

If judge gives your program output limit exceeded. then change

Code: Select all

while(scanf("%d",&n)) 
into

Code: Select all

while(1==scanf("%d",&n))
and after that you may get answers other the OLE :wink:

User avatar
Yu Fan
New poster
Posts: 26
Joined: Thu Nov 13, 2003 3:52 am

Post by Yu Fan » Thu Mar 25, 2004 1:57 pm

Thank you~~
I've got Accepted after change my code,but......
could you tell me how my code caused the output limit exceed?
:-?

Dejarik
New poster
Posts: 32
Joined: Sun Mar 07, 2004 1:23 pm
Location: Barcelona, SPAIN
Contact:

Post by Dejarik » Fri Mar 26, 2004 2:13 am

Yes, I'm also interested about the problem of using while(scanf("%d",&num)) instead of while(scanf("%d",&num)==1) because i'm receiving Output Limit Exceeded in other problem of this Set and i cannot understand where is the mistake.

Thanks in advance!

Joan

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri Mar 26, 2004 8:49 am

scanf returns EOF in case of error or end of input, a value different from 0. The statement "while(scanf(...)){...}" will loop forever at the end of input, because EOF is interpreted as the boolean TRUE.

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

10394 compiler error??

Post by oulongbin » Sun Aug 22, 2004 10:45 am

This is my code ,it runs well in VC,why i submit it will be compiler error??
[cpp]
#include <iostream>
using namespace std;
int b[20250000]={0};

void prime()
{
long i,j;
b[1]=1;
for(i=1;i<4500;i++)
if (b==0)
for(j=2;j<=20250000/i;j++)
b[i*j]=1;
}

int main()
{
long a[100010];
long cnt=1;
long i,j;
prime();
for(i=2;;i++)
{
if(b==0&&b[i+2]==0)
a[cnt++]=i;
if(cnt>100000)
break;
}
while(cin>>j)
{
cout<<"("<<a[j]<<", "<<a[j]+2<<")"<<endl;
}

return 0;
}
[/cpp]

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sun Aug 22, 2004 11:54 am

int b[20250000]={0};
Compile error could be because of this....
.... you are not allowed to declare integer array of that huge size..

you can try to covert it to character array and adjust the code accordingly to get rid of compile error. :wink:

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Aug 22, 2004 12:07 pm

You declare long a[100010] dynamically within function main(). The maximum amount of dyn. memory to be assigned within one function is someting like 64k, much less than the 400k you require.
Make it static.

Now you will probably get a "Memory Limit Exeeded" because your array int b[20250000] is over 80Meg, much more than the allowed 32Meg.
Make it an array of bytes (char or unsigned char). Or better still, pack 8 of them into the bits of a byte.

I'm not sure, but now you'll probably get "Time Limit Exeeded" because your algorithm doesn't look very fast. But I might be wrong. If so, you'll need to optimize it. Your inner loop contains one division and one multiplication. Both can be avoided. And an other thing: Do you realy have to consider even numbers for this problem?

Fuad Hassan_IIUC(DC)
New poster
Posts: 18
Joined: Fri Jan 07, 2005 9:35 pm
Location: Bangladesh

10394 WA????

Post by Fuad Hassan_IIUC(DC) » Tue Apr 19, 2005 9:44 am

plz help me :o

#include<iostream.h>
#include<stdio.h>
#include<math.h>
#define max 100000
long long seive[max];
long long pi;
long long a[max],b[max];
long long prime[max];
void genseive()
{
long i,j,sq;
sq=sqrt(max);
seive[0]=seive[1]=1;
for(i=2;i<=sq;++i)
{
for(j=i+i;j<=max;j+=i)
seive[j]=1;
}
j=-1;pi=0;
for(i=2;i<=max;++i)
{
if(seive==0)
{
prime[++j]=i;
pi++;
}
}
}

int main()
{
genseive();
long long i,j,k,l;
while(cin>>l)
{
j=0;
for(i=0;i<=pi;i++)
{
k=labs(prime-prime[i+1]);
if(k==2)
{
a[j]=prime;
b[j]=prime[i+1];
j++;
}
else continue;
}
printf("(%lld, %lld)",a[l-1],b[l-1]);
printf("\n");
}

return 0;
}
fuad

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Thu Apr 21, 2005 6:22 pm

Hi
There are so many problem's in ur programm.
- First u have to generate 20000000 prime's
- Then u have to store all the primes in a another array
- and Mind it that if (Primes and Primes[i + 2] are prime) then u will only store it
- and then take input and print the Nth twin primes

and ur seive algorithm is not correct.
This is a sample code

Code: Select all

for ( i = 2; i <= max; i++)seive[i] = 1;
for ( i = 3; i < max; i += 2)
     if ( seive[j] )
           for ( j = i + i; j < max; j += i )
                    seive[j] = 0;
MAP

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

10394 runtime error ..

Post by sunnycare » Thu May 26, 2005 5:29 am

it runs ok on my computer (dev-cpp)

help me...

Code: Select all

//10394 Twin Primes
#include <stdio.h>
#include <stdlib.h>
#include <math.h>


#define  uns32  unsigned long
#define  LONG  uns32
#define  UL  "%u"
#define  HALF  unsigned short
#define  BITS  8
#define  LCM  (2*3*5)
#define  SIEVE_SIZE  (16<<10)
#define use(x) if(x-last==2) primes[pairPos++]=last;last=x; anz++; 

double  sum=0.0;
LONG  max=0, last=2;
unsigned char sieve[SIEVE_SIZE];
LONG *index;
LONG totalPrime;
LONG primes[107407];

LONG pairPos=0;


long sievePrimes(LONG stop,LONG start=1,LONG sieveSize=SIEVE_SIZE)
{
    
    
	uns32  size, hi, h, ji, js, i, j;
	uns32  k, hj, c, cj;
	unsigned char  *prime_diff;
	unsigned char  bi, b, m;
	LONG  stlcm, ii, jj, hh, anz;
	HALF  psize;
	int  lim;
	size=sieveSize;
   	anz=0;
   	
   	
   	//j = floor( sqrt((double)stop+0.1) );
   	
   	//if (!(j&1))
    	//--j;
   	j=4471;   
    //psize = floor((1.015*j)/(log((double)j)-1)); 
    psize=612;
    index = (LONG*) malloc((sizeof(LONG)+1)*psize);
    
   	
   	prime_diff = (unsigned char*)(index+psize);

   	
    use(2);
   	
    use(3);
    
   	if (start%2 == 0)
    	start += 1;
   	if (start%3 == 0)
    	start += 2;
   	stlcm = start/LCM;
   	hh = size*(stlcm/size);
   	/*** sifting the sieve primes ***/
   	k=m=0;
   	
   	h=i=cj=0;
   	js=jj=0;
   	b=c=1;
   	
   	for(;;)
   	{
    	switch (c)
    	{
     		do
     		{
           	case 1:
            	i++;
            	if ((m+=1) >= LCM/3)
             		m -= LCM/3;
           		////////////
           		jj += h<<1;
          		++h;
            	++jj;
            	//origin code
            	//jj+=h;
            	//h++;
            	//jj+=h;
            	if (!(sieve[i]&b))
            	{
            		c= 2;
               		break;
           		}
     		case 2:
            	i++;
            	if (i == size)
            	{
                 	i=0;
                 	cj += size;
                 	//b+=b;
                 	b <<= 1;
                 	if (!b)
                  		break;
           		}
           		if ((m+=1) >= LCM/3)
             		m -= LCM/3;
           		jj += h;
           		if (!(sieve[i]&b))
           		{
                 	c= 1;
                 	break;
            	}
            }while (1);
        }
        if ((jj<<3) > stop/3)
        	break;
       	//j = 3*(cj+i)+c;
       	j=((cj+i)<<1)+cj+i+c;
       	bi= m - !!m - m/BITS;
       	prime_diff[k]= BITS*2*(j/LCM-js); /* difference of successive primes < 480 */
       	prime_diff[k] |= bi;
       	js= j/LCM;
       	index[k]= ((bi&1) != (bi>>2&1) ? 5 : 0);
       	//ii=(8*jj)/(LCM/3);
       	ii= (jj<<3)/(LCM/3);
       	if (ii < stlcm)
       		ii += j*((stlcm-ii)/j);
   		if (ii < stlcm)
   		{
     		hi = (index[k] ? 19 : 1);  /* inverse zu index[k]  ---  0 <--> 1 Argh!! */
     		//hj= js+js;
     		hj=(js<<1);
     		//ji= 2*(3*m+c);
     		ji=(((m<<1)+m+c)<<1);
     		if (ji >= LCM)  ji-=LCM,  hj++;
     		switch (c)
     		{
           		do
           		{
             	case 1:
            		ii += (hj<<1);
              		hi += (ji<<1);
              	 	while (hi >= LCM)
                 		hi -= LCM,  ii++;
                 	if (ii >= stlcm  &&  hi!=5 && hi!=25)
                  		break;
           		case 2:  
                 	ii += hj;
             		hi += ji;
                    while (hi >= LCM)
                    	hi -= LCM,  ii++;
                   	if (ii >= stlcm  &&  hi!=5 && hi!=25)
                    	break;
              	} while(1);
            }
            index[k] = (BITS*hi)/LCM;
        }

        index[k] |= BITS*(ii-hh);
        k++;
        if (jj >= size)
   		   continue;
/*** sift with prime pre-sieve ***/


   	    hi = (jj<<3);

   	    ji= ((cj+i)<<1);
   	    ++ji;
   	    hj= ((ji+c)<<1)-3;
   	    bi= 1;
   	    switch(m)
   	    {
        	do
        	{
        	case 0:
        		while(hi >= size)
                {
                 	hi -= size;
               		bi<<=1;
                    if (!bi)
                    	goto go_on;
                }
                sieve[hi] |= bi;
                hi += (j<<1);
            case 2:
       		   while(hi >= size)
                {
                    hi -= size;
                    bi<<=1;
                    if (!bi)
                 		goto go_on;
                }
                sieve[hi] |= bi;
                hi += hj;
            case 3:
                while(hi >= size)
                {
                    hi -= size;
                    bi<<=1;
                    if (!bi)
                    	goto go_on;
                }
                sieve[hi] |= bi;
                hi += ji;
            case 4:
                while(hi >= size)
                {
                    hi -= size;
                    bi<<=1;
                    if (!bi)
                    	goto go_on;
                }
                sieve[hi] |= bi;
                hi += hj;
            case 5:
                while(hi >= size)
                {
                    hi -= size;
                    bi<<=1;
                    if (!bi)
                    	goto go_on;
                }
                sieve[hi] |= bi;
                hi += ji;
            case 6:
                while(hi >= size)
                {
                    hi -= size;
                    bi<<=1;
                    if (!bi)
                    	goto go_on;
                }
                sieve[hi] |= bi;
                hi += hj;
            case 7:
                while(hi >= size)
                {
                    hi -= size;
                    bi<<=1;
                    if (!bi)
                    	goto go_on;
                }
                sieve[hi] |= bi;
                hi += (j<<1);
            case 9:
                while(hi >= size)
                {
                    hi -= size;
                    bi<<=1;
                    if (!bi)
                    	goto go_on;
                }
                sieve[hi] |= bi;
                hi += ji;
                lim= size - LCM/3*j;
                while ((int)hi < lim)
                {
                    sieve[hi] |= bi;  hi += (j<<1);
                    sieve[hi] |= bi;  hi += hj;
                    sieve[hi] |= bi;  hi += ji;
                    sieve[hi] |= bi;  hi += hj;
                    sieve[hi] |= bi;  hi += ji;
                    sieve[hi] |= bi;  hi += hj;
                    sieve[hi] |= bi;  hi += (j<<1);
                    sieve[hi] |= bi;  hi += ji;
                }
            }while (1);
            do
            {
            case 1:
                while(hi >= size)
                {
                    hi -= size;
                    bi<<=1;
                    if (!bi)
                    	goto go_on;
                }
                sieve[hi] |= bi;
                hi += ji;
            case 8:
                while(hi >= size)
                {
                    hi -= size;
                    bi<<=1;
                    if (!bi)
                       	goto go_on;
                }
                sieve[hi] |= bi;
                hi += hj;
                lim= size - LCM/3* 5;
                while ((int)hi < lim)
                {
                    sieve[hi] |= bi;
                    hi += ji;
                    sieve[hi] |= bi;  hi += hj;
                    sieve[hi] |= bi;  hi += ji;
                    sieve[hi] |= bi;  hi += hj;
                    sieve[hi] |= bi;  hi += ji;
                    sieve[hi] |= bi;  hi += hj;
                    sieve[hi] |= bi;  hi += ji;
                    sieve[hi] |= bi;  hi += hj;
                    sieve[hi] |= bi;  hi += ji;
                    sieve[hi] |= bi;  hi += hj;
                }
            }while (1);
        }
        go_on: ;

    }

/****** main sifting starts *****/
    for (i=size;i--;)
        sieve[i]=0;
    sieve[0] |= !hh;  /* 1 is not prime */
    if (start <= 5)   use(5);
    if (start%5 == 0)  start += 2*(3-start%3);
    hh *= LCM;
    while (1)
    {
        j= prime_diff[0]/BITS;
        for (h=1;h<k;h++)   /* sieve with next sieve prime (h=0 is prime 5) */
        {
            j += prime_diff[h]/BITS;
            ii = index[h]/BITS;
            if (ii >= size)
            {
                index[h] -= size*BITS;
                continue;
            }
            hj= (size <= LCM/2*j ? 0 : size - LCM/2*j);
            i=ji=js= j;
            ji +=js;
            i += ji;

            hi = ii;

            switch( prime_diff[h]%BITS )
            {
            case 0:
                switch( index[h]%BITS )
                {
                    do
                    {
                    case 0:
                        if (hi >= size)
                            goto out0;
                        sieve[hi] |=  1;  hi += i;
                    case 1:
                        if (hi >= size)
                            goto out1;
                        sieve[hi] |=  2;  hi += ji;
                    case 2:
                        if (hi >= size)
                            goto out2;
                        sieve[hi] |=  4;  hi += js;
                    case 3:
                        if (hi >= size)
                            goto out3;
                        sieve[hi] |=  8;  hi += ji;
                    case 4:
                        if (hi >= size)
                            goto out4;
                        sieve[hi] |= 16;  hi += js;
                    case 5:
                        if (hi >= size)
                            goto out5;
                        sieve[hi] |= 32;  hi += ji;
                    case 6:
                        if (hi >= size)
                            goto out6;
                        sieve[hi] |= 64;  hi += i;
                    case 7:
                        if (hi >= size)
                            goto out7;
                        sieve[hi] |=128;  hi += js+1;
                        lim= hj-1;
                        while((int)hi < lim)
                        {
                            sieve[hi] |=  1;  hi += i;
                            sieve[hi] |=  2;  hi += ji;
                            sieve[hi] |=  4;  hi += js;
                            sieve[hi] |=  8;  hi += ji;
                            sieve[hi] |= 16;  hi += js;
                            sieve[hi] |= 32;  hi += ji;
                            sieve[hi] |= 64;  hi += i;
                            sieve[hi] |=128;  hi += js+1;
                        }
                    }while (1);
                }
            case 1:
                js+=1;  i+=1;  ji+=1;
                switch( index[h]%BITS )
                {
                    do
                    {
                    case 5:
                        if (hi >= size)
                            goto out5;
                        sieve[hi] |= 32;  hi += ji;
                    case 4:
                        if (hi >= size)
                            goto out4;
                        sieve[hi] |= 16;  hi += js;
                    case 0:
                        if (hi >= size)
                            goto out0;
                        sieve[hi] |=  1;  hi += ji-1;
                    case 7:
                        if (hi >= size)
                            goto out7;
                        sieve[hi] |=128;  hi += js;
                    case 3:
                        if (hi >= size)
                            goto out3;
                        sieve[hi] |=  8;  hi += ji;
                    case 2:
                        if (hi >= size)
                            goto out2;
                        sieve[hi] |=  4;  hi += i;
                    case 6:
                        if (hi >= size)
                            goto out6;
                        sieve[hi] |= 64;  hi += js;
                    case 1:
                        if (hi >= size)
                            goto out1;
                        sieve[hi] |=  2;  hi += i;
                        lim= hj-7;
                        while((int)hi < lim)
                        {
                            sieve[hi] |= 32;  hi += ji;
                            sieve[hi] |= 16;  hi += js;
                            sieve[hi] |=  1;  hi += ji-1;
                            sieve[hi] |=128;  hi += js;
                            sieve[hi] |=  8;  hi += ji;
                            sieve[hi] |=  4;  hi += i;
                            sieve[hi] |= 64;  hi += js;
                            sieve[hi] |=  2;  hi += i;
                        }
                    }while (1);
                }
            case 2:
                i+=2;  ji+=2;
                switch( index[h]%BITS )
                {
                    do
                    {
                    case 0:
                        if (hi >= size)
                            goto out0;
                        sieve[hi] |=  1;  hi += js;
                    case 6:
                        if (hi >= size)
                            goto out6;
                        sieve[hi] |= 64;  hi += ji;
                    case 1:
                        if (hi >= size)
                            goto out1;
                        sieve[hi] |=  2;  hi += js;
                    case 7:
                        if (hi >= size)
                            goto out7;
                        sieve[hi] |=128;  hi += ji;
                    case 3:
                        if (hi >= size)
                            goto out3;
                        sieve[hi] |=  8;  hi += i;
                    case 5:
                        if (hi >= size)
                            goto out5;
                        sieve[hi] |= 32;  hi += js+1;
                    case 2:
                        if (hi >= size)
                            goto out2;
                        sieve[hi] |=  4;  hi += i;
                    case 4:
                        if (hi >= size)
                            goto out4;
                        sieve[hi] |= 16;  hi += ji;
                        lim= hj-11;
                        while((int)hi < lim)
                        {
                            sieve[hi] |=  1;  hi += js;
                            sieve[hi] |= 64;  hi += ji;
                            sieve[hi] |=  2;  hi += js;
                            sieve[hi] |=128;  hi += ji;
                            sieve[hi] |=  8;  hi += i;
                            sieve[hi] |= 32;  hi += js+1;
                            sieve[hi] |=  4;  hi += i;
                            sieve[hi] |= 16;  hi += ji;
                        }
                    }while (1);
                }
            case 3:
                js+=1;  i+=3;  ji+=1;
                switch( index[h]%BITS )
                {
                    do
                    {
                    case 5:
                        if (hi >= size)
                            goto out5;
                        sieve[hi] |= 32;  hi += ji+1;
                    case 2:
                        if (hi >= size)
                            goto out2;
                        sieve[hi] |=  4;  hi += js;
                    case 1:
                        if (hi >= size)
                            goto out1;
                        sieve[hi] |=  2;  hi += ji;
                    case 7:
                        if (hi >= size)
                            goto out7;
                        sieve[hi] |=128;  hi += i;
                    case 4:
                        if (hi >= size)
                            goto out4;
                        sieve[hi] |= 16;  hi += js;
                    case 3:
                        if (hi >= size)
                            goto out3;
                        sieve[hi] |=  8;  hi += i;
                    case 0:
                        if (hi >= size)
                            goto out0;
                        sieve[hi] |=  1;  hi += ji;
                    case 6:
                        if (hi >= size)
                            goto out6;
                        sieve[hi] |= 64;  hi += js;
                        lim= hj-13;
                        while((int)hi < lim)
                        {
                            sieve[hi] |= 32;  hi += ji+1;
                            sieve[hi] |=  4;  hi += js;
                            sieve[hi] |=  2;  hi += ji;
                            sieve[hi] |=128;  hi += i;
                            sieve[hi] |= 16;  hi += js;
                            sieve[hi] |=  8;  hi += i;
                            sieve[hi] |=  1;  hi += ji;
                            sieve[hi] |= 64;  hi += js;
                        }
                    }while (1);
                }
            case 4:
                js+=1;  i+=3;  ji+=3;
                switch( index[h]%BITS )
                {
                    do
                    {
                    case 5:
                        if (hi >= size)
                            goto out5;
                        sieve[hi] |= 32;  hi += js;
                    case 6:
                        if (hi >= size)
                            goto out6;
                        sieve[hi] |= 64;  hi += ji;
                    case 0:
                        if (hi >= size)
                            goto out0;
                        sieve[hi] |=  1;  hi += i;
                    case 3:
                        if (hi >= size)
                            goto out3;
                        sieve[hi] |=  8;  hi += js;
                    case 4:
                        if (hi >= size)
                            goto out4;
                        sieve[hi] |= 16;  hi += i;
                    case 7:
                        if (hi >= size)
                            goto out7;
                        sieve[hi] |=128;  hi += ji;
                    case 1:
                        if (hi >= size)
                            goto out1;
                        sieve[hi] |=  2;  hi += js;
                    case 2:
                        if (hi >= size)
                            goto out2;
                        sieve[hi] |=  4;  hi += ji-1;
                        lim= hj-17;
                        while((int)hi < lim)
                        {
                            sieve[hi] |= 32;  hi += js;
                            sieve[hi] |= 64;  hi += ji;
                            sieve[hi] |=  1;  hi += i;
                            sieve[hi] |=  8;  hi += js;
                            sieve[hi] |= 16;  hi += i;
                            sieve[hi] |=128;  hi += ji;
                            sieve[hi] |=  2;  hi += js;
                            sieve[hi] |=  4;  hi += ji-1;
                        }
                    }while (1);
                }
            case 5:
                js+=2;  i+=4;  ji+=2;
                switch( index[h]%BITS )
                {
                    do
                    {
                    case 0:
                        if (hi >= size)
                            goto out0;
                        sieve[hi] |=  1;  hi += ji;
                    case 4:
                        if (hi >= size)
                            goto out4;
                        sieve[hi] |= 16;  hi += i;
                    case 2:
                        if (hi >= size)
                            goto out2;
                        sieve[hi] |=  4;  hi += js-1;
                    case 5:
                        if (hi >= size)
                            goto out5;
                        sieve[hi] |= 32;  hi += i;
                    case 3:
                        if (hi >= size)
                            goto out3;
                        sieve[hi] |=  8;  hi += ji;
                    case 7:
                        if (hi >= size)
                            goto out7;
                        sieve[hi] |=128;  hi += js;
                    case 1:
                        if (hi >= size)
                            goto out1;
                        sieve[hi] |=  2;  hi += ji;
                    case 6:
                        if (hi >= size)
                            goto out6;
                        sieve[hi] |= 64;  hi += js;
                        lim= hj-19;
                        while((int)hi < lim)
                        {
                            sieve[hi] |=  1;  hi += ji;
                            sieve[hi] |= 16;  hi += i;
                            sieve[hi] |=  4;  hi += js-1;
                            sieve[hi] |= 32;  hi += i;
                            sieve[hi] |=  8;  hi += ji;
                            sieve[hi] |=128;  hi += js;
                            sieve[hi] |=  2;  hi += ji;
                            sieve[hi] |= 64;  hi += js;
                        }
                    }while (1);
                }
            case 6:
                js+=1;  i+=5;  ji+=3;
                switch( index[h]%BITS )
                {
                    do
                    {
                    case 5:
                        if (hi >= size)
                            goto out5;
                        sieve[hi] |= 32;  hi += i;
                    case 1:
                        if (hi >= size)
                            goto out1;
                        sieve[hi] |=  2;  hi += js;
                    case 6:
                        if (hi >= size)
                            goto out6;
                        sieve[hi] |= 64;  hi += i;
                    case 2:
                        if (hi >= size)
                            goto out2;
                        sieve[hi] |=  4;  hi += ji;
                    case 3:
                        if (hi >= size)
                            goto out3;
                        sieve[hi] |=  8;  hi += js;
                    case 7:
                        if (hi >= size)
                            goto out7;
                        sieve[hi] |=128;  hi += ji+1;
                    case 0:
                        if (hi >= size)
                            goto out0;
                        sieve[hi] |=  1;  hi += js;
                    case 4:
                        if (hi >= size)
                            goto out4;
                        sieve[hi] |= 16;  hi += ji;
                        lim= hj-23;
                        while((int)hi < lim)
                        {
                            sieve[hi] |= 32;  hi += i;
                            sieve[hi] |=  2;  hi += js;
                            sieve[hi] |= 64;  hi += i;
                            sieve[hi] |=  4;  hi += ji;
                            sieve[hi] |=  8;  hi += js;
                            sieve[hi] |=128;  hi += ji+1;
                            sieve[hi] |=  1;  hi += js;
                            sieve[hi] |= 16;  hi += ji;
                        }
                    }while (1);
                }
            case 7:
                js+=2;  i+=6;  ji+=4;
                switch( index[h]%BITS )
                {
                    do
                    {
                    case 0:
                        if (hi >= size)
                            goto out0;
                        sieve[hi] |=  1;  hi += js-1;
                    case 7:
                        if (hi >= size)
                            goto out7;
                        sieve[hi] |=128;  hi += i;
                    case 6:
                        if (hi >= size)
                            goto out6;
                        sieve[hi] |= 64;  hi += ji;
                    case 5:
                        if (hi >= size)
                            goto out5;
                        sieve[hi] |= 32;  hi += js;
                    case 4:
                        if (hi >= size)
                            goto out4;
                        sieve[hi] |= 16;  hi += ji;
                    case 3:
                        if (hi >= size)
                            goto out3;
                        sieve[hi] |=  8;  hi += js;
                    case 2:
                        if (hi >= size)
                            goto out2;
                        sieve[hi] |=  4;  hi += ji;
                    case 1:
                        if (hi >= size)
                            goto out1;
                        sieve[hi] |=  2;  hi += i;
                        lim= hj-29;
                        while ((int)hi < lim)
                        {
                            sieve[hi] |=  1;  hi += js-1;
                            sieve[hi] |=128;  hi += i;
                            sieve[hi] |= 64;  hi += ji;
                            sieve[hi] |= 32;  hi += js;
                            sieve[hi] |= 16;  hi += ji;
                            sieve[hi] |=  8;  hi += js;
                            sieve[hi] |=  4;  hi += ji;
                            sieve[hi] |=  2;  hi += i;
                        }
                    }while (1);
                }
            }
out0:       index[h] = 0;
            goto out;
out1:       index[h] = 1;
            goto out;
out2:       index[h] = 2;
            goto out;
out3:       index[h] = 3;
            goto out;
out4:       index[h] = 4;
            goto out;
out5:       index[h] = 5;
            goto out;
out6:       index[h] = 6;
            goto out;
out7:       index[h] = 7;
            goto out;
out:
            hi -= size;
            index[h] |= BITS*hi;

        }
/*** output of remaining (prime) numbers ***/
        i=(start<=hh ? 0 : (start-hh)/LCM);
        hh += LCM*i;
        bi= sieve[i];
        switch (start<=hh ? 0 : (BITS*(unsigned)(start-hh))/LCM)
        {
            for (;i<size;i++)
            {
                bi= sieve[i];
            case 0:
                if (!(bi&1))
                {
                    ii= hh+1;
                    if (ii > stop)
                        goto end;
                    use(ii);
                }
            case 1:
                if (!(bi&2))
                {
                    ii= hh+7;
                    if (ii > stop)
                        goto end;
                    use(ii);
                }
            case 2:
                if (!(bi&4))
                {
                    ii= hh+11;
                    if (ii > stop)
                        goto end;
                    use(ii);
                }
            case 3:
                if (!(bi&8))
                {
                    ii= hh+13;
                    if (ii > stop)
                        goto end;
                    use(ii);
                }
            case 4:
                if (!(bi&16))
                {
                    ii= hh+17;
                    if (ii > stop)
                        goto end;
                    use(ii);
                }
            case 5:
                if (!(bi&32))
                {
                    ii= hh+19;
                    if (ii > stop)
                        goto end;
                    use(ii);
                }
            case 6:
                if (!(bi&64))
                {
                    ii= hh+23;
                    if (ii > stop)
                        goto end;
                    use(ii);
                }
            case 7:
                if (!(bi&128))
                {
                    ii= hh+29;
                    if (ii > stop)
                        goto end;
                    use(ii);
                }
                hh += LCM;
                sieve[i]=0;
            }
        }
    }
end:
    free(index);
    free(sieve);
finish:
    //printf("# {"UL" <= primes <= "UL"} = "UL"\n",start,stop,anz);


    //printf("time used for sieving primes: %.3f\n",(clock()-beg)/1000.0);

    return  anz;
}
           
int main(int argc,char *argv[])
{
    sievePrimes(20000000,1);
    
    long p;
    while(scanf("%ld",&p)==1)
    {	
        printf("(%ld, %ld)\n",primes[p-1],primes[p-1]+2);
    }   	
   	
}   	

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by sumankar » Thu May 26, 2005 6:20 am

*) It's high time you rethink your algorithm
*) Dont use UL as a macro, it clashes with specifiers for integer literals
i.e.

Code: Select all

unsigned long int x = 32UL;
is valid C and instantiates x as an unsigned long whose bit pattern represents the decimal value 32.

Regards,
Suman.

User avatar
jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

Post by jaracz » Sun Jun 12, 2005 11:58 pm

my God, suman's right, you'd better rethink ya algo
keep it real!

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

Post by sunnycare » Mon Jun 13, 2005 6:08 am

the algo is right....
for i generate all prime from 1 to 20000000 ,
and check them with a corret copy.... they are the same

very strange...

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

Post by sunnycare » Mon Jun 13, 2005 6:10 am

i have accepted before..
this time i only want to make my prog faster

Post Reply

Return to “Volume 103 (10300-10399)”