[프로그래머스][LV.1] 약수의 개수와 덧셈 | python3

 

문제 링크: 약수의 개수와 덧셈

 

문제 설명

문제 설명

두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요.

제한사항
- 1 ≤ left ≤ right ≤ 1,000

 

---

문제 풀이

left부터 right까지 for문을 돌려서 각각의 수의 약수의 개수를 구한다. if문을 활용해 약수의 개수가 짝수면 그 값을 더하고 홀수면 뺀다.

chk의 처음 값을 1로 한 이유는 n의 약수에는 자기자신도 포함되기 때문이다. 약수를 구하는 과정에서 1부터 n+1//2까지만 돌기 때문에 자기자신이 빠진다. 미리 더해줘서 시작했다.  

 

내코드

def solution(left, right):
    answer = 0
    
    for n in range(left,right+1):
        chk=1
        for i in range(1,n+1//2):
            if n%i==0:
                chk+=1
        if chk%2:
            answer-=n
        else:
            answer+=n
    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

 

약수의 쌍의 특성

1. 일반적인 약수의 특징:
   • 어떤 수 nnn의 약수는 항상 **쌍(pair)**으로 존재합니다.
   • 예를 들어:
     • n=12의 약수: 1,2,3,4,6,12
       • 1×12, 2×6, 3×4 서로 짝을 이룹니다.
2. 제곱수가 아닌 경우:
   • 제곱수가 아닌 수 n에서는 약수의 쌍이 항상 서로 다릅니다.
   • 따라서 약수의 총 개수는 항상 짝수입니다.
3. 제곱수인 경우:
   • 제곱수 n에서는 약수 쌍 중에서 중복되는 약수가 하나 존재합니다.
   • 예를 들어:
     • n=9의 약수: 1,3,9
       • 3×3=9: 여기서 3은 자기 자신과 짝을 이루므로 중복됩니다.
       • 따라서 약수의 개수는 홀수입니다.

---

정리

• 제곱수가 아닌 경우: 약수는 항상 짝을 이루므로 약수의 개수는 짝수입니다.
• 제곱수인 경우: 자기 자신과 짝을 이루는 중복된 약수가 포함되므로 약수의 개수는 홀수입니다.

---

왜 제곱수에서 약수의 개수가 홀수인가?

• 제곱수는 특정 약수 kkk가 자기 자신과 곱해져 nnn이 되는 유일한 경우가 존재하기 때문입니다.
• 예: n=16:
  • 약수는 1,2,4,8,16
  • 4×4=16: 4가 중복되므로 약수 개수는 홀수(5개).

---

결론

• 제곱수를 제외한 모든 수는 약수가 짝수 개입니다.
• 이는 약수가 항상 쌍(pair)으로 존재하기 때문입니다.

 

미쳤다..... 수학능력이 뛰어나면 코드도 시간이 덜 걸리게 짤 수 있구나ㅠㅠ 찾아보니까 이해가 된다. 제곱근이 아니면 약수는 짝수개를 가지겠구나. 제곱근은 같은 수가 2번 반복되니까 그건 갯수에서 빠지는 거고...