10650 - Determinate Prime

[Adrian Kuegel]

It seems, you are too lazy to read through all this thread
So here is what I wrote 8 posts before your first post:

And please read the NB part: you should only output a maximum sequence of determinate primes, no subset of it.
So try these test cases:
251 263
251 269

For first test case you should output nothing, for second test case you should print:
251 257 263 269
As you can see, the given limits of the interval are included, so the interval given here ranges from 251 to 269 with 251 and 269 included. I think this is the usual way how "between" is used, but the problem description should have contained some word that the endpoints are included to the interval.

But your program prints:
251 257 263
251 257 263 269

[dll]

thanks to Adrian
I am sorry that I pasted a old version.
let me paste again
[cpp]
// deleted after ac
[/cpp]
But WA again

[little joey]

I gave up solving this problem as I don't know how to sort the output values (should I output "x x+2 x+4" or "x x+4 x+8" first?
moreover, I am uncertain whether I should output a series that is a subsequence of a sequence, whose biggest element is greater than 32000.
confused,
Kuba

Yes, the output is ill specified. Since this is a red flag question, the order in which the sequences are printed should be specified. To get AC, however, you should output the sequences in order of increasing first element.
Also only print one space between numbers in a sequence and no additional spaces, or you'll get PE. Also not specified.

Re your second question: can you give an example?

[LPH]

I gave up solving this problem as I don't know how to sort the output values (should I output "x x+2 x+4" or "x x+4 x+8" first?
moreover, I am uncertain whether I should output a series that is a subsequence of a sequence, whose biggest element is greater than 32000.
confused,
Kuba

Yes, the output is ill specified. Since this is a red flag question, the order in which the sequences are printed should be specified. To get AC, however, you should output the sequences in order of increasing first element.

Well, i think it is not ill specified. The very beginning of the problem says:

If three or more consecutive primes are uni-distance they are called Determinate Primes.

So we must and are only to output those sequences of primes that is consecutive(i.e. we should output 47 53 59, because it's consecutive primes; but we shoudn't output 47 59 71, because there is some prime between these three numbers.) According to this, there won't be any ambiguousity in the output.

To Kuba's 2nd problem: Since the input will not exceed 32000, and we are only have to print the sequence in the range that the input give, should we output those sequences that has some prime exceeds 32000?

[tep]

For those who got WA and have followed every hint above this msg,

I just find something and got ACC

1. I swap x and y if x > y
2. There are 162 sequences from 0 to 32000
3. Adrian Kugel's Hint
Try this test case
251 263
251 269
257 269

before my program output
251 257 263 269
257 263 269

but should be
251 257 263 269

It's wrong because we always check with the next one, without checking the previous one.

Hope helps =)

regards,
stephanus

[shihabbd81]

As you can see, the given limits of the interval are included, so the interval given here ranges from 251 to 269 with 251 and 269 included. I think this is the usual way how "between" is used, but the problem description should have contained some word that the endpoints are included to the interval.

Your task is to print all the Determinate Prime sets between two integers (inclusive)

Problem description says the interval is inclusive.

[Yoko]

My code pass in all this test and still WA

What is the prob?

[c]
#include <stdio.h>

int v[40000]; /* only to mark prime numbers */
int prime [40000]; /* prime numbers */
int p[40]; /* to print */

int main (void)
{
int i,j,k,tam,x,y,tmp,tamp,diff,t;
/* mark prime */
for (i=0;i<35000;i++)
v[i]=1;
v[1]=0;
v[0]=0;
for (i=2;i<35000;i++)
{
if (v[i]==1)
for (j=i*2;j<35000;j+=i)
v[j]=0;
}
tam = 0;
/* put the prims in primes */
for (i=0;i<35000;i++)
{
if (v[i])
{
prime[tam]=i;
tam++;
}
}
/* read input */
while (scanf("%d %d",&x,&y) == 2)
{
if (y<x) /* swap */
{
i=x; x=y; y=i;
}
i=0;
while (prime[i]<x) i++; /* jump to first */
tamp = 0;
diff = -1;
/* print sequence */
for (;prime[i]<=y;i++)
{
if (tamp == 0)
{
p[tamp]=prime[i];
tamp++;
}
else if (tamp == 1)
{
diff = prime[i]-p[0];
p[tamp] = prime[i];
tamp++;
}
else if (tamp == 2)
{
if (prime[i]-p[1]==diff)
{
p[tamp] = prime[i];
tamp++;
}
else
{
diff=-1;
p[0] = p[1];
i--;
tamp=1;
}
}
else if (tamp>=3)
{
if (prime[i]-p[tamp-1]==diff)
{
p[tamp] = prime[i];
tamp++;
}
else
{
if (!(prime[i-(tamp+1)] < x && p[0]-prime[i-(tamp+1)] == diff))
{
for (j=0;j<tamp;j++)
{
if (j==0) printf("%d",p[j]);
else printf(" %d",p[j]);
}
printf("\n");
}
diff=-1;
p[0] = p[tamp-1];
tamp=1;
i--;
}
}
}
/* if there is one more to be print */
if (tamp>=3)
{
if (prime[i]-p[tamp-1]!=diff)
{
if (!(prime[i-(tamp+1)] < x && p[0]-prime[i-(tamp+1)] == diff))
{
for (j=0;j<tamp;j++)
{
if (j==0) printf("%d",p[j]);
else printf(" %d",p[j]);
}
printf("\n");
}

}
}
}
return 0;
}
[/c]

thx

[Yoko]

[c]
#include <stdio.h>

int v[40000]; /* only to mark prime numbers */
int prime [40000]; /* prime numbers */
int p[40]; /* to print */

int main (void)
{
int i,j,k,tam,x,y,tmp,tamp,diff,t;
/* mark prime */
for (i=0;i<35000;i++)
v=1;
v[1]=0;
v[0]=0;
for (i=2;i<35000;i++)
{
if (v==1)
for (j=i*2;j<35000;j+=i)
v[j]=0;
}
tam = 0;
/* put the prims in primes */
for (i=0;i<35000;i++)
{
if (v)
{
prime[tam]=i;
tam++;
}
}
/* read input */
while (scanf("%d %d",&x,&y) == 2)
{
if (y<x) /* swap */
{
i=x; x=y; y=i;
}
i=0;
while (prime<x) i++; /* jump to first */
tamp = 0;
diff = -1;
/* print sequence */
for (;prime<=y;i++)
{
if (tamp == 0)
{
p[tamp]=prime;
tamp++;
}
else if (tamp == 1)
{
diff = prime-p[0];
p[tamp] = prime;
tamp++;
}
else if (tamp == 2)
{
if (prime-p[1]==diff)
{
p[tamp] = prime;
tamp++;
}
else
{
diff=-1;
p[0] = p[1];
i--;
tamp=1;
}
}
else if (tamp>=3)
{
if (prime[i]-p[tamp-1]==diff)
{
p[tamp] = prime[i];
tamp++;
}
else
{
if (!(prime[i-(tamp+1)] < x && p[0]-prime[i-(tamp+1)] == diff))
{
for (j=0;j<tamp;j++)
{
if (j==0) printf("%d",p[j]);
else printf(" %d",p[j]);
}
printf("\n");
}
diff=-1;
p[0] = p[tamp-1];
tamp=1;
i--;
}
}
}
/* if there is one more to be print */
if (tamp>=3)
{
if (prime[i]-p[tamp-1]!=diff)
{
if (!(prime[i-(tamp+1)] < x && p[0]-prime[i-(tamp+1)] == diff))
{
for (j=0;j<tamp;j++)
{
if (j==0) printf("%d",p[j]);
else printf(" %d",p[j]);
}
printf("\n");
}

}
}
}
return 0;
}
[/c]
Sorry for put it again... i'm new here

[Minilek]

I feel this problem needs to state explicitly that if the first number is bigger than the second number, the correct answer is not to print nothing, but rather swap and then check.

There seem to be many problems on this site where for some swapping is wrong and some it isn't, and you can't really tell until you submit and get WA.

[oulongbin]

why i always got WA??
[cpp]
#include <iostream>
using namespace std;


bool b[1000000]={0};
void prime()
{
int i,j;
b[1]=1;
for(i=1;i<1000;i++)
if (b==0)
for(j=2;j<=1000000/i;j++)
b[i*j]=1;
}

int main()
{
int i,j,k,l;
int p[3500];
int pp[200][10];
int nump[200];
int c;
int max,min;
int t;
bool f;
c=0;
prime();
for(i=2;i<32000;i++)
{
if(b==0)
p[c++]=i;
}
for(i=0,j=0;i<c;i=i+k)
{
k=0;
f=false;
t=p[i+1]-p;
l=0;
while(p[i+2+l]-p[i+1+l]==t)
{
if(k==0)
{
pp[j][0]=p;
pp[j][1]=p[i+1];
pp[j][2]=p[i+2];
k=3;

}
else
{
pp[j][k]=p[i+k];
k++;
}
l++;f=true;
}
if(f)
{
nump[j]=k;
j++;
}
else
i++;
}
while(cin>>min>>max)
{
if(min==0&&max==0)
break;
if(min>max)
{
int tt=min;
min=max;
max=tt;
}
for(i=0;i<j;i++)
{
if(pp[0]>=min&&pp[nump-1]<=max)
{
k=0;
while(k<nump)
{
cout<<pp[k]<<" ";
k++;
}
cout<<endl;
}
}
}

return 0;
}
[/cpp]

[Arm.Turbo]

Try to precalc result and find total number of such sets.
There are 162 of them.

[CodeMaker]

can anyone check my I/O? i wonder where is the mistake? is my sorting priority ok? its on difference 1st then on lexicographic.

Code: Select all

inputs:

10000 32000
1 100
500 1000
1000 500
420 540
9999 99999
101 107
80 180
963 147
789 123
357 951
0 0

Code: Select all

outputs:

10247 10253 10259
10601 10607 10613
10651 10657 10663
10847 10853 10859
11491 11497 11503
11801 11807 11813
11897 11903 11909
11927 11933 11939
12491 12497 12503
12541 12547 12553
12577 12583 12589
12641 12647 12653 12659
12967 12973 12979
13037 13043 13049
13171 13177 13183
13451 13457 13463 13469
14537 14543 14549
14741 14747 14753 14759
15187 15193 15199
15307 15313 15319
15461 15467 15473
15761 15767 15773
15791 15797 15803 15809
15901 15907 15913 15919
16091 16097 16103
16217 16223 16229
16421 16427 16433
16481 16487 16493
16561 16567 16573
16931 16937 16943
16981 16987 16993
17041 17047 17053
17321 17327 17333
17471 17477 17483 17489
18211 18217 18223 18229
18427 18433 18439
19457 19463 19469
19471 19477 19483 19489
19571 19577 19583
19597 19603 19609
20101 20107 20113
20117 20123 20129
20341 20347 20353
21157 21163 21169
21991 21997 22003
22067 22073 22079
22441 22447 22453
23321 23327 23333 23339
23761 23767 23773
23887 23893 23899
24071 24077 24083
24091 24097 24103
24407 24413 24419
24671 24677 24683
25457 25463 25469
25667 25673 25679
26171 26177 26183 26189
26387 26393 26399
26687 26693 26699
26717 26723 26729
26981 26987 26993
27061 27067 27073
27767 27773 27779
28591 28597 28603
28921 28927 28933
29167 29173 29179
29327 29333 29339
29867 29873 29879
30091 30097 30103 30109
30307 30313 30319
30631 30637 30643 30649
30971 30977 30983
31321 31327 31333
11287 11299 11311
11399 11411 11423
11719 11731 11743
12829 12841 12853
15149 15161 15173
16607 16619 16631
17419 17431 17443
17839 17851 17863
18329 18341 18353
18719 18731 18743
19727 19739 19751
19937 19949 19961
20149 20161 20173
20509 20521 20533
20719 20731 20743
21649 21661 21673
22039 22051 22063
22247 22259 22271
23789 23801 23813
25609 25621 25633
26029 26041 26053
28057 28069 28081
29587 29599 29611
30047 30059 30071
31039 31051 31063
20183 20201 20219
21893 21911 21929
25373 25391 25409
29251 29269 29287
30431 30449 30467
16763 16787 16811
3 5 7
47 53 59
557 563 569
587 593 599
601 607 613
647 653 659
727 733 739
941 947 953
971 977 983
557 563 569
587 593 599
601 607 613
647 653 659
727 733 739
941 947 953
971 977 983
10247 10253 10259
10601 10607 10613
10651 10657 10663
10847 10853 10859
11491 11497 11503
11801 11807 11813
11897 11903 11909
11927 11933 11939
12491 12497 12503
12541 12547 12553
12577 12583 12589
12641 12647 12653 12659
12967 12973 12979
13037 13043 13049
13171 13177 13183
13451 13457 13463 13469
14537 14543 14549
14741 14747 14753 14759
15187 15193 15199
15307 15313 15319
15461 15467 15473
15761 15767 15773
15791 15797 15803 15809
15901 15907 15913 15919
16091 16097 16103
16217 16223 16229
16421 16427 16433
16481 16487 16493
16561 16567 16573
16931 16937 16943
16981 16987 16993
17041 17047 17053
17321 17327 17333
17471 17477 17483 17489
18211 18217 18223 18229
18427 18433 18439
19457 19463 19469
19471 19477 19483 19489
19571 19577 19583
19597 19603 19609
20101 20107 20113
20117 20123 20129
20341 20347 20353
21157 21163 21169
21991 21997 22003
22067 22073 22079
22441 22447 22453
23321 23327 23333 23339
23761 23767 23773
23887 23893 23899
24071 24077 24083
24091 24097 24103
24407 24413 24419
24671 24677 24683
25457 25463 25469
25667 25673 25679
26171 26177 26183 26189
26387 26393 26399
26687 26693 26699
26717 26723 26729
26981 26987 26993
27061 27067 27073
27767 27773 27779
28591 28597 28603
28921 28927 28933
29167 29173 29179
29327 29333 29339
29867 29873 29879
30091 30097 30103 30109
30307 30313 30319
30631 30637 30643 30649
30971 30977 30983
31321 31327 31333
11287 11299 11311
11399 11411 11423
11719 11731 11743
12829 12841 12853
15149 15161 15173
16607 16619 16631
17419 17431 17443
17839 17851 17863
18329 18341 18353
18719 18731 18743
19727 19739 19751
19937 19949 19961
20149 20161 20173
20509 20521 20533
20719 20731 20743
21649 21661 21673
22039 22051 22063
22247 22259 22271
23789 23801 23813
25609 25621 25633
26029 26041 26053
28057 28069 28081
29587 29599 29611
30047 30059 30071
31039 31051 31063
20183 20201 20219
21893 21911 21929
25373 25391 25409
29251 29269 29287
30431 30449 30467
16763 16787 16811
151 157 163
167 173 179
151 157 163
167 173 179
251 257 263 269
367 373 379
557 563 569
587 593 599
601 607 613
647 653 659
727 733 739
941 947 953
199 211 223
151 157 163
167 173 179
251 257 263 269
367 373 379
557 563 569
587 593 599
601 607 613
647 653 659
727 733 739
199 211 223
367 373 379
557 563 569
587 593 599
601 607 613
647 653 659
727 733 739

[CodeMaker]

I missunderstood the sorting sequence, got AC after fixing it. they should have mentioned a sorting sequence for clearity.

[bijon]

why i am getting wrong answer using this code?.

Code: Select all

#include<stdio.h>
#include<math.h>
#include<iostream>
#define _swap(a,b,c){ c=a;a=b;b=c;}
#define size 33001

using namespace std;

int siv[ size ] = { 0 };
int arr[ 100 ];

void Siv()
{
	int i,j,l;
	for(i = 4;i<size;i+=2)
		siv[ i ] = 1;
	l=sqrt(size);
	for(i=3;i<=l;i+=2)
		if(siv[i]==0)
			for(j=i*i;j<size;j+=i)
				siv[j]=1;
	siv[1]=1;
}

int main(void)
{
	int i,k,p1,p2,count,j,diff,diff2;
	Siv();
	while(scanf("%d%d",&p1,&p2)==2)  //p1 is lower limit && p2 is upper limit
	{
	   if(p1==0 && p2==0)
	      return 0;
	   if(p1==0) p1=1;
	   if(p1>p2) _swap( p1, p2, diff2 );
		
		for(i=p1;i<=p2;i++)
		{
	      if( siv[ i ]==0 )
		  {
			diff2=0;
			k=i-1;
			while( siv[ k ]!=0 && k ) //check the previous distance of the prime of p1
 		     	k--;
			if(k!=0)
			  diff2=i-k;      //take the diff
			count=0;
			k=i+1;              //start from next position 
			while(siv[k]!=0)
			 k++;
			diff=k-i;           //take the prime of next one
			arr[ count ] = i;   //store first one
			count++;            
			arr[count]=k;      //store the second one
			count++;
			j=k+1;             // start from next
			while(j<=p2)
			{
			  if(siv[j]==0)
			  {
				if(j-k!=diff)   //take the difference
			      break;      //if not equal break
				arr[count]=j;   //store that
				count++;        
				k=j;
			  }
			  j++;
			}
			if(j<=p2 && count>=3)
			{
			  if(i==p1 && diff2 && diff==diff2)  //check the previous difference is eual or not
			  {
			 	i=arr[count-1]-1;
				continue;
			  }                        //if not then print the array
			  for(j=0;j<count-1;j++)
			 	cout<<arr[j]<<" ";
				cout<<arr[count-1]<<endl;
			}
			else if(j>p2)    //if j greater break means complete checking;            
				break;
			i=arr[count-1]-1;
		  }
		}
		/* check for the last prime distance from next one */
	  if(count>=3)
	  {
	   j=p2+1;
	   while(siv[j]!=0)
	    j++;
	   if(diff2 && diff!=diff2)
	     if(j-arr[count-1]!=diff)  //iff not print
		 {
	       for(j=0;j<count-1;j++)
	          cout<<arr[j]<<" ";
		      cout<<arr[count-1]<<endl;
		}
	  }
	}
return 0;
}

please help.

[Raj Ariyan]

Hi Bijon,
I also got WA before. I missed some cases. But now ACC. I've given you some of the input. Whats is the output of ur code generate ??

Code: Select all

41 18467
6334 26500
19169 15724
11478 29358
26962 24464
5705 28145
23281 16827
9961 491
2995 11942
4827 5436
391 14604
3902 153
292 12382
17421 18716
19718 19895
5447 21726
14771 11538
1869 19912
25667 26299
17035 9894
28703 23811
31322 30333
17673 4664
15141 7711
28253 6868
25547 27644
662 757
20037 12859
8723 9741
27529 778
12316 3035
22190 1842
288 30106
9040 8942
19264 22648
27446 23805
15890 6729
24370 15350
15006 31101
24393 3548
19629 12623
24084 19954
18756 11840
4966 7376
13931 26308
16944 439
24626 11323
5537 21538
16118 2082
22929 16541
4833 31115
4639 29658
22704 9930
13977 2306
31673 22386
5021 28745
26924 19072
6270 5829
26777 15573
5097 16512
23986 13290
9161 18636
22355 24767
23655 15574
4031 12052
27350 1150
16941 21724
13966 3430
31107 30191
18007 11337
15457 12287
27753 10383
14945 8909
209 9758
24221 18588
6422 24946
27506 13030
16413 29168
900 591
18762 1655
17410 6359
27624 20537
21548 6483
27595 4041
3602 24350
10291 30836
9374 11020
4596 24021
27348 23199
19668 24484
8281 4734
53 1999
26418 27938
6900 3788
18127 467
3728 14893
24648 22483
17807 2421
14310 6617
22813 9514
0 0