*****************************************************************************************
//一道QQ上的題目							    *
//												*
//兩個人A，B，數字為2～100之間的共99個自然數。	*
//現找出兩個數，把其和告訴A，把其積告訴B。然后	*
//問A知道不知道是哪兩個數，A說：“雖然我不知道	*
//，但是肯定B也不知道。”再問B，B說：“本來我	*
//不知道，但是聽到A說這句話，現在我知道了。”	*
//A聽到B說他知道了，然后就說：“現在我也知道了	*
//”。那么這兩個數是多少呢？					*
//                                              *
//----------------------------------------------*
//算法步驟:
//1.找出所有A和B都不能肯定的數，并建立一個列表
//2.從上述數表每次取出一個數c,把它進行加法拆分(a[1]+b[1],a[2]+b[2],...,a[n]+b[n])
//3.取遍每一組拆分，把每組拆分進行如下操作：
//  3-1.把a[i]與b[i]相乘，并將結果進行乘法拆分
//  3-2.把每組拆分結果分別相加
//  3-3.在列表中查看相加結果是否存在,若存在，記w為1，否則記為0
//  3-4.統計a[i]與b[i]這組分拆中w為1的次數
//4.若數c的加法分拆中只有一組a[i0]與b[i0]的w為1的次數(analysis)為1，
//  則可確定所求的兩個數就是a[i0]與b[i0]
//
//作者：Henry King & 死神
//******************************************************************************************

#include <iostream>
#include <cmath>

using namespace std;

int prime[25]={2,3,5,7,11,13,17,19,
	23,29,31,37,41,43,47,
	53,59,61,67,71,73,79,
	83,89,97};										//2～100的質數
int a,b;											//最終所求的結果
int M[199];											//所有A和B都不能肯定的數（未篩選）
int m;												//用于篩選數表的變量
int i=0,j=0;										//計數變量
int c[84];											//重新排序好的數表
int sum_s[50][2];									//存放分拆的數組
int x;												//暫存數表變量
int y,z;											//暫存加法拆分變量
int sum;											//乘法拆分相加結果
int temp,w,analysis;
void func1(int&, int&);							    //查詢函數 
void func2(int&, int&, int&);						//乘法分拆函數	

int main()
{
	for(i=0; i<=198; i++)
	{
		M[i]=i+1;									//建立1~199的數表
	}
	for(i=0; i<=24; i++)
	{
		for(j=i+1; j<=24; j++)
		{
			m=prime[i]+prime[j];
			M[m-1]=0;
		}
		m=prime[i]*(prime[i]+1);
		if(m<=198) M[m-1]=0;		   			    //找出A與B均不能肯定的數
	}
	cout << "A與B均不能肯定的數如下:\n";
	j=0;
	for(i=0; i<=198; i++)
		if(M[i]>5)
		{
			cout << M[i] <<" ";
			c[j]=M[i];
			j++;
		}										    //重新排序好的數表
	cout << "\n所求結果是:";
	for(j=0; j<=83; j++)
	{
		analysis=0;
		x=c[j];										//讀取數表中的一個數
		temp=x/2-2;
		for(i=0; i<=temp; i++)
		{
			sum_s[i][0]=i+2;
			sum_s[i][1]=x-(i+2);
			y=sum_s[i][0];
			z=sum_s[i][1];							//加法拆分
			func2(y, z, w);							//乘法拆分+查詢數表
			analysis+=w;							//統計w為1的次數
		}
		if(analysis==1) 
			cout <<	'\n' << a << " and " 
			     << b << '\n';		                //輸出結果
	}
	return 0;
}

//******************************************************************************************

void func1(int& x,int& w)
{
	int y=0;
	for(int i=0; i<=83; i++)
	{
		if(x==c[i]) y++;							//與數表對比
		else continue;
	}
	w+=y;
}

//******************************************************************************************

void func2(int& x, int& y, int& w)
{
	int product,temp;
	product=x*y;
	temp=sqrt(product);
	for(int i=2; i<=temp; i++)
	{
		if(product%i==0)
		{
			if(i!=product/i)
			sum=i+product/i;					   //乘法拆分并將結果相加
			func1(sum,w);
		}
		else continue;
	}
	if(w>=2) w=0;
	else 
	{
		a=x; 
		b=y;
	}

}

//******************************************************************************************