210716_04 약수의 개수와 덧셈_프로그래머스

프로그래머스 코딩 테스트 입니다. level_01 입니다.

약수와 관련된 문제입니다. 

약수 개수가 짝수인 값은 더하고 홀수인 값은 빼는 문제입니다.

약수 개수가 홀수인 경우는 수학에서는 제곱수일 때입니다.

제곱수를 찾아서 문제를 해결하는 방향으로 풀었습니다.

 

<문제 : https://programmers.co.kr/learn/courses/30/lessons/77884>

In [ ]:

약수의 개수와 덧셈¶

• 문제 설명

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

• 제한사항

• 1 ≤ left ≤ right ≤ 1,000

• 입출력 예

left	right	result
13	17	43
24	27	52

• 입출력 예 설명

---

• 입출력 예 #1

  • 다음 표는 13부터 17까지의 수들의 약수를 모두 나타낸 것입니다.

수	약수	약수의 개수
13	1, 13	2
14	1, 2, 7, 14	4
15	1, 3, 5, 15	4
16	1, 2, 4, 8, 16	5
17	1, 17	2

• 따라서, 13 + 14 + 15 - 16 + 17 = 43을 return 해야 합니다.

---

• 입출력 예 #2

  • 다음 표는 24부터 27까지의 수들의 약수를 모두 나타낸 것입니다.

수	약수	약수의 개수
24	1, 2, 3, 4, 6, 8, 12, 24	8
25	1, 5, 25	3
26	1, 2, 13, 26	4
27	1, 3, 9, 27	4

• 따라서, 24 - 25 + 26 + 27 = 52를 return 해야 합니다.

In [ ]:

알고리즘¶

• 약수에 대한 수학적 고찰

  • 소수부분에서도 언급했듯이 숫자는 곱의 형태로 표현됩니다.
    • 일반적으로 쌍으로 존재하는 것입니다. 즉 약수 개수가 짝수입니다.
    • 약수 개수가 홀수 : 같은 값으로 곱해지는 경우 -> 제곱인 경우입니다
    • 예 : 36 = 1x36 = 2x18 = 3x12 = 4x9 = 6x6(제곱) : 약수 개수가 홀수

• 범위 내에 있는 제곱수를 찾습니다

  • 제곱근 : sqrt()를 사용하기 위해서는 "import math"를 사용해야 합니다
    • n ** 0.5 : n의 양의 제곱근 즉 $\sqrt n$
  • 제곱수 찾기 : int(n ** 0.5) ** 2 == n
    • 아래의 "예 1"과 "예 2"를 참조해서 보시면 됩니다

• 예 1
  • n = 5
  • n ** 0.5 = 2.2
  • int(n ** 0.5) = 2
  • int(n ** 0.5) ** 2 = 2^2 = 4 : 5가 아닙니다
  • n = 5 : 제곱수가 아닙니다

• 예 2
  • n = 16
  • n ** 0.5 = 4
  • int(n ** 0.5) = 4
  • int(n ** 0.5) ** 2 = 4^2 = 16 : 16입니다
  • n = 16 : 제곱수입니다

• 범위 : 13 ~ 17
  • start_int = int(13 ** 0.5) = int(3.605) = 3
    • 13이 제곱수가 아니므로 start_int에 1을 더합니다
    • if 문으로 제곱수일 때와 아닐 때를 나눴습니다
  • end_int = int(17 ** 0.5) = int(4.123) = 4
    • 제곱수를 계산할 때 4가 포함되어야 합니다
    • 순환문 : range(start_int, end_int+1) - 이렇게 해야 4 제곱을 계산합니다
    • 아래 코드는 범위 내의 제곱수의 합을 구하는 것입니다

# python code
    for i in range(start_int, end_int+1):
        a += i*i

• 범위내의 제곱수는 4의 제곱인 16뿐입니다. 16만 약수 개수가 홀수입니다

• 결과
  • 13 ~ 17까지 모든 수를 더합니다. 16도 더했습니다.
  • 이 값에 16x2를 빼준 값을 반환하면 됩니다

In [ ]:

In [13]:

a = 3**0.5
b = 35**0.5
print(int(a), int(b))

1 5

In [ ]:

In [2]:

import math

math.sqrt(100)

Out[2]:

10.0

In [3]:

def issquare(n):
    return int(n ** 0.5) ** 2 == n

issquare(100)

Out[3]:

True

In [4]:

def issquare(n):
    if int(n**0.5)**2 == n:
        return -1
    else:
        return 1

issquare(100)

Out[4]:

-1

In [ ]:

제출한 코드입니다¶

In [14]:

def solution(left, right):
    answer = 0
    a = 0
    
    if int(left ** 0.5) ** 2 == left:
        start_int = int(left**0.5)
    else:
        start_int = int(left**0.5) + 1
        
    end_int = int(right**0.5)
    
    for i in range(left, right + 1):
        answer += i
    
    for i in range(start_int, end_int+1):
        a += i*i
    return answer - 2*a

In [15]:

print(solution(13, 17))

43