월간 코드 챌린지 시즌2
문제풀러 바로가기👇👇👇👇👇👇
코딩테스트 연습 - 약수의 개수와 덧셈
두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주
programmers.co.kr
내 풀이
def solution(left, right):
answer = 0
for i in range(left, right+1):
cnt = 1
for j in range(1, i//2+1):
if i % j == 0:
cnt += 1
answer += i if cnt % 2 == 0 else -i
return answer사실 문제 자체가 쉬워서 문제풀이가 어렵지는 않았다.
심지어 이 문제를 풀면서 약수 개수를 찾는 복잡도를 절반으로 줄였다고 좋아했었다.
(cnt에 미리 1을 넣어놓으면 본인수를 넣는 의미이기 때문에 절반까지만 반복문을 돌릴 수 있다.)
하지만 이번에 문제를 풀고 내가 몰랐던 수학적인 사실을 알게 되어서 블로그에 따로 기록하게되었다.
다른 사람 풀이
def solution(left, right):
answer = 0
for i in range(left,right+1):
if int(i**0.5)==i**0.5:
answer -= i
else:
answer += i
return answer약수가 홀수개인 모든 수는 제곱수
이 문제에서 명제 하나를 배워간다.