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

from collections import defaultdict

def isPrime(num):
    if num==1:
        return False
    end = int(num**(0.5))

    for i in range(2, end+1): #2~end
        if num%i == 0:
            return False

    return True

def Factorization(num):
    primes = defaultdict(int)      #{소인수: 지수}
    tmp=num

    for k in range(2, num+1): 
        if isPrime(k):
            while tmp%k == 0 and tmp != 0:
                primes[k] += 1
                tmp = tmp//k

    return primes

def solution(left, right):
    answer = 0

    for num in range(left, right+1):
        if num == 1:
            answer = -1
            continue

        primes = Factorization(num)   # 소인수분해

        tmp=1
        for count in primes.values(): # 약수개수 계산
            tmp *= (count+1)

        num = num if tmp%2==0 else -num
        answer += num

    return answer

<내 풀이 분석(끔찍한 풀이)>

1. 소인수분해를 해준다

2. 소인수들의 지수에 해당하는 값+1 들을 곱해준다

3. 짝수인지 확인하여 값을 더하거나 빼준다

 

 

이 문제를 풀 때 핵심

=> 제곱수의 약수의 개수는 홀수/ 제곱수가 아닌 수의 약수의 개수는 짝수이다.

 

이걸 모르면 나처럼 삽질을 할 수 있음

 

 

 

 

<알고 푼 풀이>

def solution(left, right):
    answer = 0
    sqrt = num**(0.5)
    for num in range(left, right+1):
        if int(sqrt) == sqrt:
            answer -= num
        else:
            answer += num
    return answer

코드 길이가 3배 넘게 줄었다...