약수의 개수를 구하는 알고리즘

1. 문제

 

https://programmers.co.kr/learn/courses/30/lessons/77884?language=python3 

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

 

두 정수 left와 right가 매개변수로 주어집니다.

 

left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고,

 

약수의 개수가 홀수인 수는 뺀 수를 return하도록 solution 함수를 완성해주세요.

 

 

2. 제한사항

 

$1 \leq left \leq right \leq 1000$

 

 

3. 입출력 설명

 

 

4. 나의 풀이

 

얼마전 풀었던 코딩테스트에서 본 소인수분해 알고리즘을 이용

 

소인수분해 알고리즘은 그렇게 어렵지 않다

 

주어진 수 number가 1이 아닐때까지 while문을 이용해 반복하고

 

초기 소수 init를 2로 잡고 number를 나눠

 

나누어 떨어지면 number//init를 number로 주고

 

나누어 떨어지지 않으면 init를 1 더해서 올린다

 

init = 2

while number != 1:
    
    if number % init == 0:
        
        number = number // init
        
    else:
        
        init = init + 1

 

소인수분해의 지수에 1을 더한 값을 곱하면 약수의 개수이므로

 

이것을 이용하여 left부터 right까지 약수의 수를 list로 저장

 

저장한 list에서 하나씩 빼서 약수의 개수가 짝수인지 홀수인지 검사하여 더하고 빼서 최종 answer를 출력

 

def solution(left, right):
    
    answer = 0
    
    number_list = []
    
    for number in rnage(left, right+1):
        
        num = number
        
        divisor = 1
        
        exp = 0
        
        init = 2
        
        ## 소인수분해
        
        while number != 1:
            
            if number % init == 0:
                
                number = number // init
                
                exp = exp + 1
                
            else:
                
                init = init + 1
                
                ## 지수에 1을 더해 곱해나가면 약수의 개수가 된다
                
                divisor = divisor * (exp + 1)
                
                exp = 0
                
        divisor = divisor * (exp + 1)
        
        number_list.append((num,divisor))
        
    for num,divisor in number_list:
    
        if divisor % 2 == 0:
            
            answer = answer + num
            
        else:
        
            answer = answer - num
            
    return answer

 

 

5. 다른 풀이

 

제곱수의 약수의 개수는 홀수이고 그렇지 않은 수는 짝수개임을 이용

 

def solution(left, right):

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

 

제곱수인지 검사하는 기술이 멋진데

 

제곱수일려면 1/2제곱을 하더라도 정수여야한다는 사실을 이용해서

 

int(((number)**0.5))와 ((number)**0.5)가 같은지 아닌지를 검사

 

isinstance( a, int)도 생각할 수 있지만 int(((number)**0.5))이 float여서 이 방법은 통하지 않아

 

 

6. 되돌아보기

 

-------------------------------------------------------------------------------------

6-1) 소인수분해 알고리즘

 

초기 소수를 2로 잡고 주어진 수를 1이 아닐때까지 반복해서 소수로 나눈다

 

나누어 떨어지면 주어진 수를 소수로 나누고 나눠진 값으로 주어진 수를 갱신

 

나누어 떨어지지 않으면 소수 값에 1을 더한다

 

-------------------------------------------------------------------------------------

 

6-2) 약수의 수는 모든 소인수들의 지수에 1을 더한 값들을 곱한다

 

-------------------------------------------------------------------------------------

6-3) 제곱수의 약수의 수는 홀수개이고 제곱수가 아닌 수의 약수의 수는 짝수개이다

 

-------------------------------------------------------------------------------------

 

6-4) 제곱수인지 아닌지 검사하는 방법으로 int(((number)**0.5)) == ((number)**0.5)

 

정수인지 검사하는 기법으로 생각보다 자주 쓰임