Page 4 of 7

10394 Output Limit Execeed

Posted: Wed Mar 24, 2004 12:41 pm
by Yu Fan
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;
}

Posted: Thu Mar 25, 2004 7:33 am
by Subeen
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:

Posted: Thu Mar 25, 2004 1:57 pm
by Yu Fan
Thank you~~
I've got Accepted after change my code,but......
could you tell me how my code caused the output limit exceed?
:-?

Posted: Fri Mar 26, 2004 2:13 am
by Dejarik
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

Posted: Fri Mar 26, 2004 8:49 am
by little joey
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.

10394 compiler error??

Posted: Sun Aug 22, 2004 10:45 am
by oulongbin
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]

Posted: Sun Aug 22, 2004 11:54 am
by sohel
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:

Posted: Sun Aug 22, 2004 12:07 pm
by little joey
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?

10394 WA????

Posted: Tue Apr 19, 2005 9:44 am
by Fuad Hassan_IIUC(DC)
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;
}

Posted: Thu Apr 21, 2005 6:22 pm
by mohiul alam prince
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

10394 runtime error ..

Posted: Thu May 26, 2005 5:29 am
by sunnycare
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);
    }   	
   	
}   	

Posted: Thu May 26, 2005 6:20 am
by sumankar
*) 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.

Posted: Sun Jun 12, 2005 11:58 pm
by jaracz
my God, suman's right, you'd better rethink ya algo

Posted: Mon Jun 13, 2005 6:08 am
by sunnycare
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...

Posted: Mon Jun 13, 2005 6:10 am
by sunnycare
i have accepted before..
this time i only want to make my prog faster