[프로그래머스] 약수의 개수와 덧셈

---

문제설명

https://programmers.co.kr/learn/courses/30/lessons/77884

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

사고과정

• 소수 판별이나 소수의 개수를 구하는 에라토스테네스의 체 처럼 제곱근을 활용해서 탐색하는 시간 복잡도를 줄일 수 있지 않을까를 계속 파고들었다.. 하지만 결국 구현을 하지 못해서 그냥 1부터 X까지 선형적으로 약수를 탐색했다.
• 다른사람 풀이를 보니 약수가 홀수개인 모든 수는 제곱수라는 것을 이용해서 풀 수 있었다. 문제에서는 어차피 X의 약수 개수가 무엇인지 묻기보다는 홀수 개수인지 짝수 개수인지만 묻는 것이므로 약수가 홀수개인 모든 수는 제곱수라는 명제를 이용해 풀이했다.(단, 모든 제곱수 -> 약수가 홀수개 라는 명제는 아니다. 반대만 성립한다고 함. 프로그래머스 질문에 나와있었다)

풀이

- 다른 사람의 풀이(math 라이브러리 사용하지 않고 0.5를 제곱해서 제곱근 만드는 것도 잊어먹었던 문법을 알게 해준 듯)

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

- 나의 풀이(단지 선형적으로 탐색)

import math

def count_divisor(x):
    cnt = 0
    for i in range(1, x+1):
        if x % i == 0:
            cnt += 1
    return cnt


def solution(left, right):
    answer = 0
    for x in range(left, right+1):
        cnt = count_divisor(x)
        if cnt % 2 == 0:
            answer += x
        else:
            answer -= x
    return answer