s先生与p先生谜题.cpp

历史上著名的p先生和s先生谜题

#include<stdio.h>
#include<math.h>
#define MAXNUM 100

//记录满足第一句话的两个数的和
//s[p]=0表示表示满足一句话条件的两个数的和
//否则表示不满足
int SA[2*MAXNUM - 1]; 

//记录满足第二句话的乘积的两个数
//A[p][q]=0表示满足第二句话的乘积的两个数p和q
//否则表示不满足 
int A[MAXNUM][MAXNUM];

//最后满足三句话条件的两个数  
int x = 0,y = 0;

void init();  //初始化函数
void searchSA();  //寻找满足第一句话条件的SA
void searchA();   //寻找满足第二句话条件的A
void searchResult();  //寻找满足三句话的两个数
bool isPrimeNum(int m,int n);  //判断m*n的乘积是否只能由m和n相乘得到


int main()
{
	init();
	searchSA();
	searchA();
	searchResult();
	return 0;
}


//初始化函数
void init()
{
	int i = 0,j = 0;
	for(i = 0;i < (2*MAXNUM - 1);i++)
	{
		SA[i] = 0;
	}
	for(i = 0;i < MAXNUM;i++)
		for(j = 0;j < MAXNUM;j++)
		{
			A[i][j] = 0;
		}
}


//寻找满足第一句话条件的SA
void searchSA()
{
	int i = 0,j = 0,counter=0;

	for(i = 4;i < (2*MAXNUM - 1);i++)
	{
		counter=0;

		for(j = 2;j <= (i/2) && j < MAXNUM;j++)
		{
			if( (i-j) < MAXNUM && j < MAXNUM )
			{
				counter++;
				//不满足第一句话的情形
				if(isPrimeNum( j,(i - j) ) )
				{
					SA[i] = 1;
					break;
				}
			}
		}
        //不满足第一句话的情形
		if(counter == 1)
		{
			SA[i]=1;
		}
	}
}


//寻找满足第二句话条件的A
void searchA()
{
	int i = 0,j = 0,k = 0,counter = 0;

	for(i = 2;i <= (MAXNUM - 1);i++)
		for(j = 2;j <= (MAXNUM - 1);j++)
		{
			counter=0;

			for(k = 2;k <= (i*j/2) && k < MAXNUM;k++)
			{
				if( (i*j)%k==0 && (i*j)/k < MAXNUM && k<MAXNUM )
				{
					if( SA[ (i*j)/k + k ] == 0 )
					{
						counter++;
					}
				}
			}
			//不满足第二句话的情形
			if(counter!=1&&counter!=2)
			{
				A[i][j]=1;
				A[j][i]=1;
			}
		}
}


//寻找满足三句话的两个数
void searchResult()
{
	int i = 0,j = 0,counter=0;

	for(i = 4;i < (2*MAXNUM - 1);i++)
	{
		if(SA[i] == 0)
		{
			counter = 0;

			for(j = 2;j <= (i/2) && j < MAXNUM;j++)
			{
				if(counter > 1)
					break;

				if((i-j) < MAXNUM && j < MAXNUM && A[i-j][j] == 0)
				{
					counter++;
					x=i-j;
					y=j;
				}
			}
			//满足三个条件的情形的解输出
			if(counter == 1)
			{
				printf("%d %d\n",x,y);
			}
		}
	}
}


//判断m*n的乘积是否只能由m和n相乘得到
bool isPrimeNum(int m,int n)
{
	int i = 0,temp1=0,temp2=0;


	//********************************
	//分别找m和n的因子
	for(i = 2;i <= sqrt(m);i++)
	{
		if(m%i == 0)
		{
			temp1=i;
			break;
		}
	}
	for(i = 2;i <= sqrt(n);i++)
	{
		if(n%i == 0)
		{
			temp2=i;
			break;
		}
	}
	//*********************************


	//两个都为质数的情形
	if(temp1==0&&temp2==0)
	{
		return true;
	}

	
	//*************************************
	//一个为质数一个为非质数的情形
	if(temp1!=0&&temp1*n>=MAXNUM&&temp2==0)
	{
		return true;
	}
	if(temp2!=0&&temp2*m>=MAXNUM&&temp1==0)
	{
		return true;
	}
	//*************************************


	//两个为非质数的情形
	if(temp1!=0&&temp2!=0&&temp1*n>=MAXNUM&&temp2*m>=MAXNUM)
	{
		return true;
	}


	//以上的情形都不满足的情形返回false
	return false;

}