첫번째 버전에서 향상된 점.
1) 루트값까지만 검사함으로써 시간 단축.
2) 입력값이 소수인지 확인하는 코드가 제일 앞에 있었는데, 소수 값이 클 경우, 속도가 느려지므로, 인수분해를 해서 되지 않으면 소수로 판정하고 해당 값을 반환함. 가령 입력값이 13이면 {13:1}
3) 인수분해를 한번 했으면, 이전 코드에서는 나누는 수(제수)를 2로 초기화했는데, 한번 나누었으면 그 수보다 작은 수로 다시 인수분해되는 경우는 없을 것이므로, 나눈 수에서 재시작. 가령 2부터 시작해서 나눠보다가 5로 나눠지면, 5로 나눈 몫을 다시 NUM으로 설정하고 5부터 나누기 시도함.(이전에는 다시 2부터 나누기 시작했었음)
결과: 소인수가 큰 수일 경우, 처리 속도가 이전 버전에 비해 2배 정도 빨라졌음.
############ 효율적인 알고리즘
# 인수분해를 해서 결과를 딕셔너리로 반환
# 가령 인수분해 결과가 2^3 * 3^2 * 7 이라면
# {2:3, 3:2, 7:1} 반환
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