카테고리 없음
(정수론/파이썬) 곱셈완전수를 판정하는 두 가지 방법
미친토끼
2021. 9. 15. 13:40
# '친절한 수론 길라잡이' 연습문제 15.6
# 곱셈완전수
# "완전수는 자신의 진약수의 합과 같다. 만일, 합 대신 곱의 경우를 고려할 때, 우리는 어떤 수가 자신의 진약수의
# 곱과 같을 때, 이를 곱셈완전수(product perfect)라 이름짓자. 예를 들어
# m 진약수들의 곱
# 6 1*2*3 = 6 곱셈완전수
# 9 1*3 = 3
# 12 1*2*3*4*6 = 144
# 15 1*3*5 = 15 곱셈완전수
# a) 2와 50 사이의 곱셈완전수를 모두 찾아보아라."
# 소수 판정 함수. 소수면 True, 아니면 False 반환
def isPrime(num):
root_val = round(num ** 0.5) # 제곱근 값을 구한다
for i in range(2, root_val+1): # 제곱근값+1 까지만 약수를 조사해도 충분하다
if num % i == 0: # 중간에 나눠지면 소수가 아니다
return False
return True
# 소인수분해를 해주는 함수
def factorize2(value):
num = value # 원래값을 보존한다.
divisor_primes = [] # 분해된 인수를 차곡차곡 저장하는 리스트
factorize_dict = {} # 리스트의 원소 갯수를 세어 넣는 용도
# num이 소수라면 (num, 1)을 딕셔너리에 넣어 반환한다.
# if isPrime(num):
# factorize_dict[num] = 1
# return factorize_dict
root_val = int(num ** 0.5)+1
# 인수분해 루틴은 소수 판정 루틴과는 조금 다르게 접근할 필요가 있다.
i = 2
found = False
while True:
# 소수 검증 때처럼 num까지 모두 나누어볼 필요는 없고 제곱근값 까지만 나누어보면 된다.
if i >= root_val: break
# i가 소수인지 검사해서 소수라면 num을 i로 나눈다
# i로 나눠서 나머지가 0이라면, 인수분해가 한번 된 것이다.
if isPrime(i) and num % i == 0:
divisor_primes.append(i) # 나누는 수를 저장
num = num // i # 몫, 가령 24//2 = 12
#print(f"{i}, {num}")
root_val = int(num ** 0.5)+1
if found == False:
found = True # 찾았다는 표시를 함
# 12는 소수가 아니므로 반복문 계속. 소수가 나오면 그 소수를 저장하고 반복문 종료.
if isPrime(num):
divisor_primes.append(num)
break # return divisor_primes
#i = 2 # 인수분해를 한번 했으므로 숫자를 다시 2부터 나눠보기로 설정
else:
i += 1 # 인수분해가 되지 않으면 젯수(나누는 수)를 1증가
#print(divisor_primes)
for n in divisor_primes:
if n in factorize_dict:
factorize_dict[n] += 1
else:
factorize_dict[n] = 1
if found == False: # 소인수를 못 찾았다면 소수이므로
factorize_dict[value] = 1
return factorize_dict
# 약수 구하는 함수: 향상된 버전
# 소인수분해 결과를 가지고 약수를 만듦
# 숫자가 클 경우, 속도 면에서 단순한 방식(버전1)보다 훨씬 빠름
# 50234902430546664의 약수를 구했을 때 버전2가 1초 걸리고, 버전1이 35초 걸림.
def getDivisor2(num):
divisors = []
res = factorize2(num) # 예) {2:3, 3:2, 7:1} 형태
for key, value in res.items():
divisor = []
for i in range(value+1):
divisor.append(key**i)
divisors.append(divisor)
# divisors : [[2**0, 2**1, 2**2, 2**3], [3**0, 3**1, 3**2], [7**0, 7**1]]
# divisors : [[1, 2, 4, 8], [1, 3, 9], [1, 7]]
while True:
tmp = [] # 리스트 2개 원소를 서로 곱해서 약수를 만들어 임시 저장
# 리스트를 하나씩 줄여나가는데 리스트가 하나만 남았으면 그것이 약수 집합이므로 종료한다
if len(divisors) < 2:
break
# 리스트 2개의 각 원소를 서로 곱해서 약수를 만들어 저장
for n in divisors[0]:
for m in divisors[1]:
tmp.append(n * m)
# divisors 안의 리스트는 예에서 3개이고, 리스트[0]과 [1]을 곱해서 약수를 만들고(tmp),
# 기존 리스트[0]과 리스트 [1]을 삭제하고 1차 약수 리스트인 tmp를 리스트[0] 자리에 끼워넣는다.
# 한번 실행을 거치면 이제 리스트 목록은 총 2개가 되었다.
del divisors[0] # 원래 divisors[0] 삭제
del divisors[0] # 원래 divisors[1] 삭제
divisors.insert(0, tmp) # 생성된 tmp를 divisors 제일 앞에 끼워넣기
# 원래는 아래의 인덱싱 방식으로 코딩을 하다가, 그냥 원소를 하나씩 나열해서 처리하는 것이
# 훨씬 나을 것 같았다. 실제로도 나았고...
#for j in range(len(divisors[0])): # 0~3
# for k in range(len(divisors[1])): # 0~2
# tmp.append(divisors[0][j] * divisors[1][k]) # [0][0] * [1][0]
return sorted(divisors[0]) # 리스트의 리스트이므로 바깥 대괄호를 제거하고 정렬해서 반환
# 해당 숫자가 곱셈완전수인지 판정하는 함수
# 소인수분해 방식으로 약수를 모두 구해 자신을 제외하고 모두 곱한다.
# 그 값이 자기 자신과 동일하면 곱셈완전수로 판정한다.
def isProductPerfect(num):
# 약수를 모두 구하기
divisors = getDivisor2(num) # 약수를 모두 구하기 (소인수분해 방식)
divisors.remove(num) # 전체 약수에서 자기 자신을 제외
gop = 1
for d in divisors: # 약수를 모두 곱한다.
gop *= d
if gop != num: # 원 수와 다르면
return False, gop
else: # 원 수와 같으면
return True, gop
# 연습문제 15.6.a
# 2와 51 사이의 곱셈완전수를 모두 찾는다
for n in range(2, 51):
print(n, isProductPerfect(n))
'''출력
...
6 (True, 6)
...
26 (True, 26)
27 (True, 27)
28 (False, 784)
29 (False, 1)
30 (False, 27000)
'''
# 약수의 개수만 구하는 함수
# 소인수분해해서 지수를 가지고 갯수를 구한다.
def divisorsCount(num):
divisors = factorize2(num) #{2:3, 3:2, 7:1} 형태
# 인수에는 관심없고 각기 지수에 1을 더해 모두 곱한다.
gop = 1
for p, e in divisors.items():
gop *= e + 1 # 4
return gop
# 연습문제 15.6.b
# 소인수 지수만 가지고 갯수를 계산해서 곱셈완전수인지를 확인하는 코드와,
# 약수를 모두 구해 직접 곱해서 곱셈완전수인지를 확인하는 코드를 비교한다.
# 약수가 4개면 곱셈완전수가 된다. 6을 예로 들면 약수는 [1, 2, 3, 6]이다.
# 자신(6)을 제외한 수를 다 곱하면 가운데 두 수(2, 3)의 곱과 같고, 이것은 자신(6)과 같다.
# 약수의 개수가 6개면 자신^2, 8개면 자신^3 이 된다.
# 일반화하면, 자신^(약수의개수/2 - 1) # 지수에서 1을 빼는 것은 약수들의 곱에서 (1 * 자신)을 제외하기 때문이다
list_divisorsCount = [] # 약수 개수만 구해서 저장
list_isProductPerfect = []
for n in range(2, 100):
if divisorsCount(n) == 4: # 곱셈완전수는 약수 갯수가 4개이다
list_divisorsCount.append(n)
if isProductPerfect(n)[0] == True: # 약수를 일일이 찾아 곱셈완전수인지 판정하는 함수를 호출
list_isProductPerfect.append(n)
print(list_divisorsCount)
print(list_isProductPerfect)
print(list_divisorsCount == list_isProductPerfect) # 두 함수 사용 결과가 동일한지 확인실행결과:
2 (False, 1)
3 (False, 1)
4 (False, 2)
5 (False, 1)
6 (True, 6)
7 (False, 1)
8 (True, 8)
9 (False, 3)
10 (True, 10)
11 (False, 1)
12 (False, 144)
13 (False, 1)
14 (True, 14)
15 (True, 15)
16 (False, 64)
17 (False, 1)
18 (False, 324)
19 (False, 1)
20 (False, 400)
21 (True, 21)
22 (True, 22)
23 (False, 1)
24 (False, 13824)
25 (False, 5)
26 (True, 26)
27 (True, 27)
28 (False, 784)
29 (False, 1)
30 (False, 27000)
31 (False, 1)
32 (False, 1024)
33 (True, 33)
34 (True, 34)
35 (True, 35)
36 (False, 279936)
37 (False, 1)
38 (True, 38)
39 (True, 39)
40 (False, 64000)
41 (False, 1)
42 (False, 74088)
43 (False, 1)
44 (False, 1936)
45 (False, 2025)
46 (True, 46)
47 (False, 1)
48 (False, 5308416)
49 (False, 7)
50 (False, 2500)
[6, 8, 10, 14, 15, 21, 22, 26, 27, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95]
[6, 8, 10, 14, 15, 21, 22, 26, 27, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95]
True