相亲数--Python

　　想亲数：在遥远的古代，人们发现某些自然数之间有特殊的关系：如果两个数a和b，a的所有除本身以外的因数之和等于b，b的所有除本身以外的因数之和等于a，则称a,b是一对相亲数

code:

 def sumFunc(n):   #这个是求真因数的和，真因数不包括自己

     a = 1

     b = n

     sum = 0

     while a < b:

         if n % a == 0:

             sum += (a + b)

         a += 1

         b = n / a

     if a == b and n % a == 0:

         sum += a

     return sum - n

 for x in range(2,10000):

     y = sumFunc(x)

     if x < y and x == sumFunc(y):

         print(x,"<-相亲数->",y)

这个求的是 2~10000 范围的想亲数

然后这里里面其实可以改进，由于一个数可能会多次求真因数，我们就可以浪费空间，将已经求取真因数的数存到字典里，并且将求取的值作为valuse。

 cache = {}

 def sumFunc(n):   #这个是求真因数的和，真因数不包括自己

     res = cache.get(n,0)  #如果没有取到这个value的值就返回0

     if res:

         return res

     a = 1

     b = n

     sum = 0

     while a < b:

         if n % a == 0:

             sum += (a + b)

         a += 1

         b = n / a

     if a == b and n % a == 0:

         sum += a

     cache[n] = sum

     return sum - n

 for x in range(2,10000):

     y = sumFunc(x)

     if x < y and x == sumFunc(y):

         print(x,"<-相亲数->",y)

我们其实可以导入时间模块，来计算一下这两个算法时间的快慢，程序开始使用 time.time() ,程序结束的时候在使用一次 time.time() ,然后计算差值就可以了

巴特西

相亲数--Python

最新文章

热门文章