花了一天，想明白一道题。
孙膑，庞涓都是鬼谷子的徒弟；一天鬼出了这道题目：他从2到99中选出两个不同的整数，把积告诉孙，把和告诉庞。
庞说：我虽然不能确定这两个数是什么，但是我肯定你也不知道这两个数是什么。
孙说：我本来的确不知道，但是听你这么一说，我现在能够确定这两个数字了。
庞说：既然你这么说，我现在也知道这两个数字是什么了。
问这两个数字是什么？为什么？
水木的IQDoor有这个题的解法，但我觉得他的分析有问题。"我肯定你也不知道这两个数是什么"这句话能说明"x+y一定不能表示成2个质数之和"？我觉得不对，严谨的说应该是x+y一定不能表示成2个2~99之间的质数之和。
因为庞知道的数字x+y也许可以分解成两个质数之和(这就不能用Goldbach Conjecture了)，但这两个质数有一个不在2~99的范围，而符合范围的分解中没有质数组合，庞就可以确定孙不知道答案。
想了很久还是不知道怎么手算，最后写了个程序。
用isSumOfPrime(x)==true表示x可以表示成2个2~99之间的质数之和
所以分析第一句话
"我不能确定这两个数是什么"，排除2+3,2+4,97+99,98+99
"但是我肯定你也不知道这两个数是什么"，isSumOfPrime(x+y)==false。
站在孙的角度考虑，他的数字x×y有很多因式分解的方式，他通过庞的话排除掉了不可能的情况，得到最终的结果。那什么情况不可能？
如果分解为a×b，那么庞手中的数字是a+b，则需要有isSumOfPrime(a+b)==false，如果isSumOfPrime(a+b)==true，则可以排除a×b的情况
孙通过庞的第一句话知道了结果，说明在所有a×b的分解中，只有一组isSumOfPrime(a+b)==false
把满足这种条件的num=a×b，表示为onlyOneFactorization(num)==true
分析第三句话，站在庞的角度考虑，他得到的数字x+y表示成2个数字的和有很多种方式。在所有的x+y=a+b的分解中，那种分解方式是对的呢？
如果分解为a+b，那么孙的数字应该是a×b，那么应该有onlyOneFactorization(a×b)==true，如果onlyOneFactorization(a×b)==false，则可以排除分解为a+b的情况
然后既然庞说他知道结果了，那么说明根据上面的猜测，他排除了足够多的分解情况，最终只剩下一组分解的方式。
把满足这种条件的num=a+b，表示为onlyOneDivision(num)==true
用庞可能拿到的数字着手进行逐个测试，
RANGE=100
isSumOfPrime=[]
prime=[]
failSet=set([])
succeedSet=set([])
def primes(n):
if n==2: return [2]
elif n<2: return []
s=range(3,n+1,2)
mroot = n ** 0.5
half=(n+1)/2-1
i=0
m=3
while m <= mroot:
if s[i]:
j=(m*m-3)/2
s[j]=0
while j<half:
s[j]=0
j+=m
i=i+1
m=2*i+3
return [2]+[x for x in s if x]
def onlyOneFactorization(num):
#对于测试过的num，放入成功集或失败集，避免多次测试
if num in failSet:
return False
if num in succeedSet:
return True
findOne=False
finda=0
findb=0
for i in range(2,int(num**0.5+1)):
if num%i==0:
a=i
b=num/i
if b < RANGE and a<b and not isSumOfPrime[a+b]:
if findOne==False:
findOne=True
finda=a
findb=b
else:
failSet.add(num)
return False #找到不止一种a×b分解方法
if findOne :
succeedSet.add(num)
return findOne
def onlyOneDivision(num):
findOne=False
finda=0
findb=0
for i in range(2,int(num/2+1)):
a=i
b=num-i
if b < RANGE and a<b and onlyOneFactorization(a*b):
if findOne==False:
findOne=True
finda=a
findb=b
else:
return False #找到不止一种a+b分解方法
if findOne:
print "x+y= ",num," x*y= ",finda*findb," x= ",finda," y= ",findb
return findOne
if __name__ == '__main__':
#用数组来保存isSumOfPrime,查找快捷
prime=primes(RANGE)
isSumOfPrime=[False for i in range(RANGE*2)]
for i in range(0,len(prime)):
for j in range(i+1,len(prime)):
isSumOfPrime[prime[i]+prime[j]]=True
#排除5,6,197,198四种情况
for i in range(7,2×RANGE-4):
if isSumOfPrime[i]: #是2个质数之和，跳过
continue
onlyOneDivision(i)
最终结果只有一组，x+y= 17 x*y= 52 x= 4 y= 13
Last modified on 2007-10-16