-
약수의 개수, 약수의 합 공식개발자의 길/Algorithm 2021. 3. 27. 21:18
고등학교 수학 시간에 배우는 소인수 분해 후 약수의 개수와 합을 구하는 공식을 이용해서 코드를 작성해보자.
위에 코드를 조금 개선해서 만들어 보자.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647import mathdef solution(n):prime = [] # n보다 작은 소수를 담는 리스트# n보다 작거나 같은 모든 소수 중 n을 나누는 것만 prime에 담는다.for i in [2, 3]:if n % i == 0:prime.append(i)for i in range(5, n + 1, 2): # 2이상의 소수는 모두 홀수flag = Truefor j in prime:if j > math.sqrt(i): break # i의 제곱근 보다 작은 소수에 대해서만 확인if i % j == 0:flag = Falsebreakif flag and n % i == 0: prime.append(i)# 소인수 분해 과정을 통해 각 소인수의 지수와 부분합 구하기exponent = []temp = []for i in prime:k = nj = 0 # 각 소인수의 지수while k % i == 0:j += 1k //= iexponent.append(j) # 구한 지수를 리스트에 담는다.# 등비수열 합 공식을 이용해서 각 소인수 마다 부분합 구한다. 1부터 더하므로 총 항의 개수는 j + 1 개이다.partial_sum = (i ** (j + 1) - 1) // (i - 1)temp.append(partial_sum)# 약수의 개수 구하기divisor = 1for i in exponent:divisor *= (i + 1)# 약수의 합 구하기sum_of_divisor = 1for j in temp:sum_of_divisor *= jreturn divisor, sum_of_divisorcs 테스트 결과 잘 된다.
'개발자의 길 > Algorithm' 카테고리의 다른 글
124나라의 숫자 (프로그래머스, 레벨2) (0) 2021.04.01 프로그래머스 연습문제 레벨1 클리어 (0) 2021.03.30 소수 만들기 (프로그래머스, 레벨1) (0) 2021.03.27 약수의 합 (프로그래머스, 레벨1), 양의 약수의 합 공식 (0) 2021.03.17 큰 수 만들기 (프로그래머스, 레벨2) (0) 2021.03.12