想亲数: 在遥远的古代, 人们发现某些自然数之间有特殊的关系: 如果两个数 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() , 然后计算差值就可以了
来源: http://www.bubuko.com/infodetail-2737224.html