[파이썬/python] 약수의 개수와 덧셈 - 제곱수는 약수의 갯수가 홀수.

설명 부분은 모르겠는 부분이나 정리하고 싶은 부분을 gpt에게 물어본 것입니다. 개인 공부용.

약수의 개수와 덧셈 - 제곱수는 약수의 갯수가 홀수.

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

#내 풀이
def solution(left, right):
    answer = 0
    for num in range(left,right+1):
        cnt = 0  
        for j in range(1,num+1):
            if num % j == 0:
                cnt += 1
        if cnt % 2 == 0:
            answer += num
        elif cnt %2 != 0:
            answer -= num
            
    return answer

#남 풀이 
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 solution(left, right):
    answer = 0
    for num in range(left,right+1):
        if int(math.sqrt(num)) == math.sqrt(num): #제곱근이 정수이면 약수가 홀수개
            answer -= num
        else:
            answer += num
                
    return answer
 

주어진 코드에서 if int(i**0.5)==i**0.5: 부분은 i의 제곱근이 정수인지를 확인하는 조건문임. 이 조건문이 왜 약수의 개수와 관련이 있는지 설명할게.

코드 분석

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

제곱근이 정수인 경우

• 제곱수는 약수의 개수가 홀수임.
  • 예를 들어, 9의 약수는 1, 3, 9로 3개이고, 그 중 3은 중복되므로 약수의 개수가 홀수임.
  • 16의 약수는 1, 2, 4, 8, 16으로 5개이고, 그 중 4와 8은 중복되므로 역시 약수의 개수가 홀수임.
• 일반적으로, 약수는 짝수개가 됨. 예를 들어 12의 약수는 1, 2, 3, 4, 6, 12로 6개임. 하지만 제곱수의 경우는 하나의 약수가 두 번 등장하지 않아서 약수의 개수가 홀수임.

if int(i**0.5) == i**0.5: 의 역할

• i**0.5는 i의 제곱근을 의미함.
• int(i**0.5)는 제곱근을 정수로 변환한 값.
• i**0.5와 int(i**0.5)가 같으면, i는 제곱수임. 즉, 약수의 개수가 홀수임.

따라서, 제곱수일 경우 answer -= i로 빼기를 하고, 제곱수가 아닐 경우 answer += i로 더하기를 함.

결론

• 제곱수(약수의 개수가 홀수인 경우)는 answer에서 빼고, 그 외의 수(약수의 개수가 짝수인 경우)는 answer에 더함.
• int(i**0.5) == i**0.5는 i가 제곱수인지 아닌지를 확인하는 조건문이고, 이 조건을 통해 약수의 개수를 홀수/짝수로 구분함.

네, 맞습니다! 제곱수가 아닌 수는 약수의 개수가 짝수임.

제곱수의 약수 개수가 홀수인 이유를 더 자세히 설명할게요.

약수의 쌍

• 어떤 수 n의 약수는 대개 쌍을 이루어서 존재합니다.
  • 예를 들어, 12의 약수는 1, 12, 2, 6, 3, 4처럼 각 약수가 쌍을 이뤄 존재합니다. 즉, 1과 12, 2와 6, 3과 4는 서로 곱해서 12가 되기 때문에, 약수의 개수는 짝수입니다.

제곱수의 특성

• 제곱수는 하나의 약수가 두 번 등장하는 특성이 있습니다.
  • 예를 들어, 36은 6^2이므로 36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36입니다. 여기서 중요한 점은 6이 하나의 약수로 두 번 등장한다는 것입니다. 6은 6 * 6 = 36이기 때문에, 6은 두 번 나오게 되죠.
  • 이런 이유로 제곱수의 약수는 한 쌍을 이루지 않는 약수가 존재하게 되어, 약수의 개수가 홀수가 됩니다.

예시

1. 12의 약수

12는 제곱수가 아니므로 약수의 개수가 짝수입니다.

• 약수: 1, 2, 3, 4, 6, 12
• 쌍: (1, 12), (2, 6), (3, 4)
• 개수: 6개 (짝수)

2. 36의 약수

36은 제곱수입니다. 6^2 = 36이므로 6은 두 번 등장합니다.

• 약수: 1, 2, 3, 4, 6, 9, 12, 18, 36
• 쌍: (1, 36), (2, 18), (3, 12), (4, 9), 6
• 개수: 9개 (홀수)

결론

• 제곱수는 하나의 약수가 두 번 등장하기 때문에, 약수의 개수가 홀수입니다.
• 제곱수가 아닌 수는 각 약수가 한 쌍을 이루기 때문에 약수의 개수가 짝수입니다.