anti-primesequences.cpp

判断数列相邻n项和是否为和数

/*Problem
Given a sequence of consecutive integers n,n+1,n+2,...,m, an anti-prime sequence is a rearrangement of these integers
 so that each adjacent pair of integers sums to a composite (non-prime) number. For example, if n = 1 and m = 10, 
one such anti-prime sequence is 1,3,5,4,2,6,9,7,8,10. This is also the lexicographically first such sequence. 
We can extend the definition by defining a degree danti-prime sequence as one where all consecutive subsequences of 
length 2,3,...,d sum to a composite number. The sequence above is a degree 2 anti-prime sequence, but not a degree 3,
 since the subsequence 5, 4, 2 sums to 11. The lexicographically .rst degree 3 anti-prime sequence for these numbers is
 1,3,5,4,6,2,10,8,7,9. 



Input
Input will consist of multiple input sets. Each set will consist of three integers, n, m, and d on a single line. 
The values of n, m and d will satisfy 1 <= n < m <= 1000, and 2 <= d <= 10. The line 0 0 0 will indicate end of input 
and should not be processed.

Output
For each input set, output a single line consisting of a comma-separated list of integers forming a degree danti-prime 
sequence (do not insert any spaces and do not split the output over multiple lines). In the case where more than one 
anti-prime sequence exists, print the lexicographically first one (i.e., output the one with the lowest first value; 
in case of a tie, the lowest second value, etc.). In the case where no anti-prime sequence exists, output 

No anti-prime sequence exists. 




Sample input
1 10 2
1 10 3
1 10 5
40 60 7
0 0 0

Sample output
1,3,5,4,2,6,9,7,8,10
1,3,5,4,6,2,10,8,7,9
No anti-prime sequence exists.
40,41,43,42,44,46,45,47,48,50,55,53,52,60,56,49,51,59,58,57,54
*/
#include<iostream>
using namespace std;
int m,n,d;
int a[1000]={0};//数字是否被占用
int b[1000]={0};//数字是几
int k=0;//选出第几个数
int s[9956];//合数表

int composite(int q)//判定某数是否合数

{
	return s[q];
}
int prime(int k,int d)//判定单一度数
{
	if((k+1)<d)return 1;
	
		int q=0;
		for(int w=k-d+1;w<=k;w++)
		{
			q=q+b[w];
		}
		
		if(!composite(q))return 0;
	
	return 1;
}
int judge(int k,int d)//检查数列度数
{
	int a;
	for(int i=2;i<=d;i++)
	{
		a=prime(k,i);
		if(a==0)return 0;
	}
	return 1;
}

void search(int k)//选数
{
	
	if(b[k]==0)
	{
		for(int i=0;i<m-n+1;i++)
			if(a[i]==1);
		    else
		    {
			a[i]=1;
			b[k]=i+n;
			break;
			}
	}
	
	else
	{
		int y=b[k]-n;
		a[b[k]-n]=0;b[k]=0;
		for(int w=y+1;w<m-n+1;w++)
			if(a[w]==1);
		    else
		    {
			a[w]=1;
			b[k]=w+n;
			break;
			}
	}
	//cout<<k<<"k"<<b[k]<<"b[k]"<<endl;//tiaosji
}
int main()
{
	s[2]=0;
s[3]=0;
s[4]=1;
s[5]=0;
s[6]=1;
s[7]=0;
s[8]=1;
s[9]=1;
s[10]=1;
s[11]=0;
s[12]=1;
s[13]=0;
s[14]=1;
s[15]=1;
s[16]=1;
s[17]=0;
s[18]=1;
s[19]=0;
s[20]=1;
s[21]=1;
s[22]=1;
s[23]=0;
s[24]=1;
s[25]=1;
s[26]=1;
s[27]=1;
s[28]=1;
s[29]=0;
s[30]=1;
s[31]=0;
s[32]=1;
s[33]=1;
s[34]=1;
s[35]=1;
s[36]=1;
s[37]=0;
s[38]=1;
s[39]=1;
s[40]=1;
s[41]=0;
s[42]=1;
s[43]=0;
s[44]=1;
s[45]=1;
s[46]=1;
s[47]=0;
s[48]=1;
s[49]=1;
s[50]=1;
s[51]=1;
s[52]=1;
s[53]=0;
s[54]=1;
s[55]=1;
s[56]=1;
s[57]=1;
s[58]=1;
s[59]=0;
s[60]=1;
s[61]=0;
s[62]=1;
s[63]=1;
s[64]=1;
s[65]=1;
s[66]=1;
s[67]=0;
s[68]=1;
s[69]=1;
s[70]=1;
s[71]=0;
s[72]=1;
s[73]=0;
s[74]=1;
s[75]=1;
s[76]=1;
s[77]=1;
s[78]=1;
s[79]=0;
s[80]=1;
s[81]=1;
s[82]=1;
s[83]=0;
s[84]=1;
s[85]=1;
s[86]=1;
s[87]=1;
s[88]=1;
s[89]=0;
s[90]=1;
s[91]=1;
s[92]=1;
s[93]=1;
s[94]=1;
s[95]=1;
s[96]=1;
s[97]=0;
s[98]=1;
s[99]=1;
s[100]=1;
s[101]=0;
s[102]=1;
s[103]=0;
s[104]=1;
s[105]=1;
s[106]=1;
s[107]=0;
s[108]=1;
s[109]=0;
s[110]=1;
s[111]=1;
s[112]=1;
s[113]=0;
s[114]=1;
s[115]=1;
s[116]=1;
s[117]=1;
s[118]=1;
s[119]=1;
s[120]=1;
s[121]=1;
s[122]=1;
s[123]=1;
s[124]=1;
s[125]=1;
s[126]=1;
s[127]=0;
s[128]=1;
s[129]=1;
s[130]=1;
s[131]=0;
s[132]=1;
s[133]=1;
s[134]=1;
s[135]=1;
s[136]=1;
s[137]=0;
s[138]=1;
s[139]=0;
s[140]=1;
s[141]=1;
s[142]=1;
s[143]=1;
s[144]=1;
s[145]=1;
s[146]=1;
s[147]=1;
s[148]=1;
s[149]=0;
s[150]=1;
s[151]=0;
s[152]=1;
s[153]=1;
s[154]=1;
s[155]=1;
s[156]=1;
s[157]=0;
s[158]=1;
s[159]=1;
s[160]=1;
s[161]=1;
s[162]=1;
s[163]=0;
s[164]=1;
s[165]=1;
s[166]=1;
s[167]=0;
s[168]=1;
s[169]=1;
s[170]=1;
s[171]=1;
s[172]=1;
s[173]=0;
s[174]=1;
s[175]=1;
s[176]=1;
s[177]=1;
s[178]=1;
s[179]=0;
s[180]=1;
s[181]=0;
s[182]=1;
s[183]=1;
s[184]=1;
s[185]=1;
s[186]=1;
s[187]=1;
s[188]=1;
s[189]=1;
s[190]=1;
s[191]=0;
s[192]=1;
s[193]=0;
s[194]=1;
s[195]=1;
s[196]=1;
s[197]=0;
s[198]=1;
s[199]=0;
s[200]=1;
s[201]=1;
s[202]=1;
s[203]=1;
s[204]=1;
s[205]=1;
s[206]=1;
s[207]=1;
s[208]=1;
s[209]=1;
s[210]=1;
s[211]=0;
s[212]=1;
s[213]=1;
s[214]=1;
s[215]=1;
s[216]=1;
s[217]=1;
s[218]=1;
s[219]=1;
s[220]=1;
s[221]=1;
s[222]=1;
s[223]=0;
s[224]=1;
s[225]=1;
s[226]=1;
s[227]=0;
s[228]=1;
s[229]=0;
s[230]=1;
s[231]=1;
s[232]=1;
s[233]=0;
s[234]=1;
s[235]=1;
s[236]=1;
s[237]=1;
s[238]=1;
s[239]=0;
s[240]=1;
s[241]=0;
s[242]=1;
s[243]=1;
s[244]=1;
s[245]=1;
s[246]=1;
s[247]=1;
s[248]=1;
s[249]=1;
s[250]=1;
s[251]=0;
s[252]=1;
s[253]=1;
s[254]=1;
s[255]=1;
s[256]=1;
s[257]=0;
s[258]=1;
s[259]=1;
s[260]=1;
s[261]=1;
s[262]=1;
s[263]=0;
s[264]=1;
s[265]=1;
s[266]=1;
s[267]=1;
s[268]=1;
s[269]=0;
s[270]=1;
s[271]=0;
s[272]=1;
s[273]=1;
s[274]=1;
s[275]=1;
s[276]=1;
s[277]=0;
s[278]=1;
s[279]=1;
s[280]=1;
s[281]=0;
s[282]=1;
s[283]=0;
s[284]=1;
s[285]=1;
s[286]=1;
s[287]=1;
s[288]=1;
s[289]=1;
s[290]=1;
s[291]=1;
s[292]=1;
s[293]=0;
s[294]=1;
s[295]=1;
s[296]=1;
s[297]=1;
s[298]=1;
s[299]=1;
s[300]=1;
s[301]=1;
s[302]=1;
s[303]=1;
s[304]=1;
s[305]=1;
s[306]=1;
s[307]=0;
s[308]=1;
s[309]=1;
s[310]=1;
s[311]=0;
s[312]=1;
s[313]=0;
s[314]=1;
s[315]=1;
s[316]=1;
s[317]=0;
s[318]=1;
s[319]=1;
s[320]=1;
s[321]=1;
s[322]=1;
s[323]=1;
s[324]=1;
s[325]=1;
s[326]=1;
s[327]=1;
s[328]=1;
s[329]=1;
s[330]=1;
s[331]=0;
s[332]=1;
s[333]=1;
s[334]=1;
s[335]=1;
s[336]=1;
s[337]=0;
s[338]=1;
s[339]=1;
s[340]=1;
s[341]=1;
s[342]=1;
s[343]=1;
s[344]=1;
s[345]=1;
s[346]=1;
s[347]=0;
s[348]=1;
s[349]=0;
s[350]=1;
s[351]=1;
s[352]=1;
s[353]=0;
s[354]=1;
s[355]=1;
s[356]=1;
s[357]=1;
s[358]=1;
s[359]=0;
s[360]=1;
s[361]=1;
s[362]=1;
s[363]=1;
s[364]=1;
s[365]=1;
s[366]=1;
s[367]=0;
s[368]=1;
s[369]=1;
s[370]=1;
s[371]=1;
s[372]=1;
s[373]=0;
s[374]=1;
s[375]=1;
s[376]=1;
s[377]=1;
s[378]=1;
s[379]=0;
s[380]=1;
s[381]=1;
s[382]=1;
s[383]=0;
s[384]=1;
s[385]=1;
s[386]=1;
s[387]=1;
s[388]=1;
s[389]=0;
s[390]=1;
s[391]=1;
s[392]=1;
s[393]=1;
s[394]=1;
s[395]=1;
s[396]=1;
s[397]=0;
s[398]=1;
s[399]=1;
s[400]=1;
s[401]=0;
s[402]=1;
s[403]=1;
s[404]=1;
s[405]=1;
s[406]=1;
s[407]=1;
s[408]=1;
s[409]=0;
s[410]=1;
s[411]=1;
s[412]=1;
s[413]=1;
s[414]=1;
s[415]=1;
s[416]=1;
s[417]=1;
s[418]=1;
s[419]=0;
s[420]=1;
s[421]=0;
s[422]=1;
s[423]=1;
s[424]=1;
s[425]=1;
s[426]=1;
s[427]=1;
s[428]=1;
s[429]=1;
s[430]=1;
s[431]=0;
s[432]=1;
s[433]=0;
s[434]=1;
s[435]=1;
s[436]=1;
s[437]=1;
s[438]=1;
s[439]=0;
s[440]=1;
s[441]=1;
s[442]=1;
s[443]=0;
s[444]=1;
s[445]=1;
s[446]=1;
s[447]=1;
s[448]=1;
s[449]=0;
s[450]=1;
s[451]=1;
s[452]=1;
s[453]=1;
s[454]=1;
s[455]=1;
s[456]=1;
s[457]=0;
s[458]=1;
s[459]=1;
s[460]=1;
s[461]=0;
s[462]=1;
s[463]=0;
s[464]=1;
s[465]=1;
s[466]=1;
s[467]=0;
s[468]=1;
s[469]=1;
s[470]=1;
s[471]=1;
s[472]=1;
s[473]=1;
s[474]=1;
s[475]=1;
s[476]=1;
s[477]=1;
s[478]=1;
s[479]=0;
s[480]=1;
s[481]=1;
s[482]=1;
s[483]=1;
s[484]=1;
s[485]=1;
s[486]=1;
s[487]=0;
s[488]=1;
s[489]=1;
s[490]=1;
s[491]=0;
s[492]=1;
s[493]=1;
s[494]=1;
s[495]=1;
s[496]=1;
s[497]=1;
s[498]=1;
s[499]=0;
s[500]=1;
s[501]=1;
s[502]=1;
s[503]=0;
s[504]=1;
s[505]=1;
s[506]=1;
s[507]=1;
s[508]=1;
s[509]=0;
s[510]=1;
s[511]=1;
s[512]=1;
s[513]=1;
s[514]=1;
s[515]=1;
s[516]=1;
s[517]=1;
s[518]=1;
s[519]=1;
s[520]=1;
s[521]=0;
s[522]=1;
s[523]=0;
s[524]=1;
s[525]=1;
s[526]=1;
s[527]=1;
s[528]=1;
s[529]=1;
s[530]=1;
s[531]=1;
s[532]=1;
s[533]=1;
s[534]=1;
s[535]=1;
s[536]=1;
s[537]=1;
s[538]=1;
s[539]=1;
s[540]=1;
s[541]=0;
s[542]=1;
s[543]=1;
s[544]=1;
s[545]=1;
s[546]=1;
s[547]=0;
s[548]=1;
s[549]=1;
s[550]=1;
s[551]=1;
s[552]=1;
s[553]=1;
s[554]=1;
s[555]=1;
s[556]=1;
s[557]=0;
s[558]=1;
s[559]=1;
s[560]=1;
s[561]=1;
s[562]=1;
s[563]=0;
s[564]=1;
s[565]=1;
s[566]=1;
s[567]=1;
s[568]=1;
s[569]=0;
s[570]=1;
s[571]=0;
s[572]=1;
s[573]=1;
s[574]=1;
s[575]=1;
s[576]=1;
s[577]=0;
s[578]=1;
s[579]=1;
s[580]=1;
s[581]=1;
s[582]=1;
s[583]=1;
s[584]=1;
s[585]=1;
s[586]=1;
s[587]=0;
s[588]=1;
s[589]=1;
s[590]=1;
s[591]=1;
s[592]=1;
s[593]=0;
s[594]=1;
s[595]=1;
s[596]=1;
s[597]=1;
s[598]=1;
s[599]=0;
s[600]=1;
s[601]=0;
s[602]=1;
s[603]=1;
s[604]=1;
s[605]=1;
s[606]=1;
s[607]=0;
s[608]=1;
s[609]=1;
s[610]=1;
s[611]=1;
s[612]=1;
s[613]=0;
s[614]=1;
s[615]=1;
s[616]=1;
s[617]=0;
s[618]=1;
s[619]=0;
s[620]=1;
s[621]=1;
s[622]=1;
s[623]=1;
s[624]=1;
s[625]=1;
s[626]=1;
s[627]=1;
s[628]=1;
s[629]=1;
s[630]=1;
s[631]=0;
s[632]=1;
s[633]=1;
s[634]=1;
s[635]=1;
s[636]=1;
s[637]=1;
s[638]=1;
s[639]=1;
s[640]=1;
s[641]=0;
s[642]=1;
s[643]=0;
s[644]=1;
s[645]=1;
s[646]=1;
s[647]=0;
s[648]=1;
s[649]=1;
s[650]=1;
s[651]=1;
s[652]=1;
s[653]=0;
s[654]=1;
s[655]=1;
s[656]=1;
s[657]=1;
s[658]=1;
s[659]=0;
s[660]=1;
s[661]=0;
s[662]=1;
s[663]=1;
s[664]=1;
s[665]=1;
s[666]=1;
s[667]=1;
s[668]=1;
s[669]=1;
s[670]=1;
s[671]=1;
s[672]=1;
s[673]=0;
s[674]=1;
s[675]=1;
s[676]=1;
s[677]=0;
s[678]=1;
s[679]=1;
s[680]=1;
s[681]=1;
s[682]=1;
s[683]=0;
s[684]=1;
s[685]=1;
s[686]=1;
s[687]=1;
s[688]=1;
s[689]=1;
s[690]=1;
s[691]=0;
s[692]=1;
s[693]=1;
s[694]=1;
s[695]=1;
s[696]=1;
s[697]=1;
s[698]=1;
s[699]=1;
s[700]=1;
s[701]=0;
s[702]=1;
s[703]=1;
s[704]=1;
s[705]=1;
s[706]=1;
s[707]=1;
s[708]=1;
s[709]=0;
s[710]=1;
s[711]=1;
s[712]=1;
s[713]=1;
s[714]=1;
s[715]=1;
s[716]=1;
s[717]=1;
s[718]=1;
s[719]=0;
s[720]=1;
s[721]=1;
s[722]=1;
s[723]=1;
s[724]=1;
s[725]=1;
s[726]=1;
s[727]=0;
s[728]=1;
s[729]=1;
s[730]=1;
s[731]=1;
s[732]=1;
s[733]=0;
s[734]=1;
s[735]=1;
s[736]=1;
s[737]=1;
s[738]=1;
s[739]=0;
s[740]=1;
s[741]=1;
s[742]=1;
s[743]=0;
s[744]=1;
s[745]=1;
s[746]=1;
s[747]=1;
s[748]=1;
s[749]=1;
s[750]=1;
s[751]=0;
s[752]=1;
s[753]=1;
s[754]=1;
s[755]=1;
s[756]=1;
s[757]=0;
s[758]=1;
s[759]=1;
s[760]=1;
s[761]=0;
s[762]=1;
s[763]=1;
s[764]=1;
s[765]=1;
s[766]=1;
s[767]=1;
s[768]=1;
s[769]=0;
s[770]=1;
s[771]=1;
s[772]=1;
s[773]=0;
s[774]=1;
s[775]=1;
s[776]=1;
s[777]=1;
s[778]=1;
s[779]=1;
s[780]=1;
s[781]=1;
s[782]=1;
s[783]=1;
s[784]=1;
s[785]=1;
s[786]=1;
s[787]=0;
s[788]=1;
s[789]=1;
s[790]=1;
s[791]=1;
s[792]=1;
s[793]=1;
s[794]=1;
s[795]=1;
s[796]=1;
s[797]=0;
s[798]=1;
s[799]=1;
s[800]=1;
s[801]=1;
s[802]=1;
s[803]=1;
s[804]=1;
s[805]=1;
s[806]=1;
s[807]=1;
s[808]=1;
s[809]=0;
s[810]=1;
s[811]=0;
s[812]=1;
s[813]=1;
s[814]=1;
s[815]=1;
s[816]=1;
s[817]=1;
s[818]=1;
s[819]=1;
s[820]=1;
s[821]=0;
s[822]=1;
s[823]=0;
s[824]=1;
s[825]=1;
s[826]=1;
s[827]=0;
s[828]=1;
s[829]=0;
s[830]=1;
s[831]=1;
s[832]=1;
s[833]=1;
s[834]=1;
s[835]=1;
s[836]=1;
s[837]=1;
s[838]=1;
s[839]=0;
s[840]=1;
s[841]=1;
s[842]=1;
s[843]=1;
s[844]=1;
s[845]=1;
s[846]=1;
s[847]=1;
s[848]=1;
s[849]=1;
s[850]=1;
s[851]=1;
s[852]=1;
s[853]=0;
s[854]=1;
s[855]=1;
s[856]=1;
s[857]=0;
s[858]=1;
s[859]=0;
s[860]=1;
s[861]=1;
s[862]=1;
s[863]=0;
s[864]=1;
s[865]=1;
s[866]=1;
s[867]=1;
s[868]=1;
s[869]=1;
s[870]=1;
s[871]=1;
s[872]=1;
s[873]=1;
s[874]=1;
s[875]=1;
s[876]=1;
s[877]=0;
s[878]=1;
s[879]=1;
s[880]=1;
s[881]=0;
s[882]=1;
s[883]=0;
s[884]=1;
s[885]=1;
s[886]=1;
s[887]=0;
s[888]=1;
s[889]=1;
s[890]=1;
s[891]=1;
s[892]=1;
s[893]=1;
s[894]=1;
s[895]=1;
s[896]=1;
s[897]=1;
s[898]=1;
s[899]=1;
s[900]=1;
s[901]=1;
s[902]=1;
s[903]=1;
s[904]=1;
s[905]=1;
s[906]=1;
s[907]=0;
s[908]=1;
s[909]=1;
s[910]=1;
s[911]=0;
s[912]=1;
s[913]=1;
s[914]=1;
s[915]=1;
s[916]=1;
s[917]=1;
s[918]=1;
s[919]=0;
s[920]=1;
s[921]=1;
s[922]=1;
s[923]=1;
s[924]=1;
s[925]=1;
s[926]=1;
s[927]=1;
s[928]=1;
s[929]=0;
s[930]=1;
s[931]=1;
s[932]=1;
s[933]=1;
s[934]=1;
s[935]=1;
s[936]=1;
s[937]=0;
s[938]=1;
s[939]=1;
s[940]=1;
s[941]=0;
s[942]=1;
s[943]=1;
s[944]=1;
s[945]=1;
s[946]=1;
s[947]=0;
s[948]=1;
s[949]=1;
s[950]=1;
s[951]=1;
s[952]=1;
s[953]=0;
s[954]=1;
s[955]=1;
s[956]=1;
s[957]=1;
s[958]=1;
s[959]=1;
s[960]=1;
s[961]=1;
s[962]=1;
s[963]=1;
s[964]=1;
s[965]=1;
s[966]=1;
s[967]=0;
s[968]=1;
s[969]=1;
s[970]=1;
s[971]=0;
s[972]=1;
s[973]=1;
s[974]=1;
s[975]=1;
s[976]=1;
s[977]=0;
s[978]=1;