DAY 16
3
Software Development

## Day16- Project1- 數字世界的朋友與戀人 (趣味數論問題: 友好數、婚約數)

2+3變成的5代表結婚，

6的因數有1, 2, 3, 6，
6除了自己之外的因數和恰好是1+2+3=6，

# 友好數、婚約數

220 自身外的正因數和為1+2+4+5+10+11+20+22+44+55+110=284
284 自身外的正因數和為1+2+4+71+142=220

48除了1和本身的正因數相加是：2+3+4+6+8+12+16+24=75，
75除了1和本身的正因數相加是：3+5+15+25=48。

# 第一步: 求出整數的正因數和

n的因數就是可以整除n的數字。

``````def divisorsum(n):
return sum([i for i in range(1,n) if n%i==0])
``````

# 第二步: 雖然非主軸但順便教大家求完美數

``````def isPerfect(n):
return divisorsum(n) == n
``````

``````for i in range(1,10000):
if isPerfect(i):
print(i)
``````

`6`
`28`
`496`
`8128`

# 第三步: 更有效率的求出整數的正因數和

``````for i in range(1,100000):
if isPerfect(i):
print(i)
``````

``````30 = 1*30
= 2*15
= 3*10
= 5*6
``````

(兩個大於根號n的數相乘一定大於n)

``````>>> 2 ** 0.5
1.4142135623730951
>>> 4 ** 0.5
2.0
>>> 9 ** 0.5
3.0
``````

``````>>> 30 ** 0.5
5.477225575051661
>>> int(30 ** 0.5)
5
``````

``````def divisorsum(n):
return sum([sum([i,n//i]) for i in range(1,int(n**0.5)+1) if n%i==0])-n
``````

(假設n是30)

``````print([[i,30//i] for i in range(1,int(30**0.5)+1) if 30%i==0])
``````

「根號9」這個因數會被重複計算，

``````print([{i,9//i} for i in range(1,int(9**0.5)+1) if 9%i==0])
``````

``````def divisorsum(n):
return sum([sum({i,n//i}) for i in range(1,int(n**0.5)+1) if n%i==0])-n
``````

# 第四步: 求出小於十萬的友好數數對

``````print([(i,divisorsum(i)) for i in range(1,7)])
``````

`[(1, 0), (2, 1), (3, 1), (4, 3), (5, 1), (6, 6)]`

1(除了自身)的正因數和=0，
2(除了自身)的正因數和=1，

6(除了自身)的正因數和=6。

`divisorsum(220)=284``divisorsum(284)=220`

``````def DS(n):
return sum([sum({i,n//i}) for i in range(1,int(n**0.5)+1) if n%i==0])-n
``````

``````def amicablePair(k):
return [(i,DS(i)) for i in range(1,k+1) if DS(DS(i))==i]
``````

``````print(amicablePair(300))
``````

6和28本身是完全數也被收納進來了，

(6, 6)因為是同一個數，

``````def amicablePair(k):
return [(i,DS(i)) for i in range(1,k+1) if i< DS(i) and DS(DS(i))==i]
``````

``````print(amicablePair(300))
``````

``````print(amicablePair(100000))
``````

# 第五步: 舉一反三- 求出小於十萬的婚約數數對

``````def DS2(n):
return sum([sum({i,n//i}) for i in range(1,int(n**0.5)+1) if n%i==0])-n-1
``````

``````def betrothedPair(k):
return [(i,DS2(i)) for i in range(1,k+1) if i< DS2(i) and DS2(DS2(i))==i]
``````

``````print(betrothedPair(100000))
``````

# 第六步: 大功告成，總結所有程式碼

``````def DS(n):
return sum([sum({i,n//i}) for i in range(1,int(n**0.5)+1) if n%i==0])-n

def DS2(n):
return sum([sum({i,n//i}) for i in range(1,int(n**0.5)+1) if n%i==0])-n-1

def findPerfect(k):
return [i for i in range(1,k+1) if DS(i) == i]

def amicablePair(k): #求小於k的友好數對
return [(i,DS(i)) for i in range(1,k+1) if i< DS(i) and DS(DS(i))==i]

def betrothedPair(k): #求小於k的婚約數對
return [(i,DS2(i)) for i in range(1,k+1) if i< DS2(i) and DS2(DS2(i))==i]

print(findPerfect(100000))
print(amicablePair(100000))
print(betrothedPair(100000))
``````

`[6, 28, 496, 8128]`
`[(220, 284), (1184, 1210), (2620, 2924), (5020, 5564), (6232, 6368), (10744, 10856), (12285, 14595), (17296, 18416), (63020, 76084), (66928, 66992), (67095, 71145), (69615, 87633), (79750, 88730)]`
`[(48, 75), (140, 195), (1050, 1925), (1575, 1648), (2024, 2295), (5775, 6128), (8892, 16587), (9504, 20735), (62744, 75495)]`

## 名字彩蛋

Python真是太有魅力了。

Day13的範例13-3好像留有判斷質數如何更有效率的問題未解。

# 課後練習

## 解法一

``````def isPrime(n):
return len([i for i in range(1,n+1) if n%i==0])==2
``````

## 解法二

``````def isPrime(n):
return sum([1 if n%i==0 else 0 for i in range(1,n+1)])==2
``````

1. 希望檢測到1以外的因數提早結束程式 (例如100可以被2整除，便不必再檢查3,4,5...可否整除100)
2. 檢查到根號n以下的數能否整除n即可 (原因與今日教的優化找正因數和的效率相同)

## 習題: 優化找質數效率

``````for i in range(1,20):
print(f'{i}是質數?: {isPrime(i)}')
``````

``````1是質數?: False
2是質數?: True
3是質數?: True
4是質數?: False
5是質數?: True
6是質數?: False
7是質數?: True
8是質數?: False
9是質數?: False
10是質數?: False
11是質數?: True
12是質數?: False
13是質數?: True
14是質數?: False
15是質數?: False
16是質數?: False
17是質數?: True
18是質數?: False
19是質數?: True
``````

### 1 則留言

0
sowhat1124
iT邦新手 5 級 ‧ 2020-09-28 18:17:43

``````def amicablePair(k): #求小於k的友好數對
return [(i,DS(i)) for i in range(1,k+1) if DS(DS(i))==i and i< DS(i)]

def betrothedPair(k): #求小於k的婚約數對
return [(i,DS2(i)) for i in range(1,k+1) if DS2(DS2(i))==i and i< DS2(i)]
``````