碎碎念

花了一天，想明白一道题。 孙膑，庞涓都是鬼谷子的徒弟；一天鬼出了这道题目：他从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=100isSumOfPrime=[]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 findOneif __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