[프로그래머스 연습문제] 약수의 개수와 덧셈

월간 코드 챌린지 시즌2

문제풀러 바로가기👇👇👇👇👇👇

약수의 개수와 덧셈

코딩테스트 연습 - 약수의 개수와 덧셈

 

 

 

내 풀이

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

약수가 홀수개인 모든 수는 제곱수

이 문제에서 명제 하나를 배워간다.