[Level.0] 순서쌍의 개수

문제 설명: 순서쌍이란 두 개의 숫자를 순서를 정하여 짝지어 나타낸 쌍으로 (a, b)로 표기합니다. 자연수 n이 매개변수로 주어질 때 두 숫자의 곱이 n인 자연수 순서쌍의 개수를 return하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ n ≤ 1,000,000

문제 해결

def solution(n):
    count = 0
    for a in range(1, n+1):
        if n%a == 0:
            count += 1
    return count


def solution(n):
    count = 0
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            count += 2
        if i * i == n:
            count -= 1
    return count

 

주석: 위의 것은 n까지 전부다 검사하는 반면에 아랫 것은 √n 만큼만 검사함(예: n = 20 이면 4.472? 정도가 나오는데 이를 int() 씌워서 소수점을 버리고 +1을 수행해 5까지만 수행함)

 

그렇다면 왜 제곱근 까지만 검사하는 것인가?

 

n = 36라면 위의 방법으로 18번의 반복문을 수행한다.

아래의 방법으로는 36**0.5 = 6번만 수행한다.(36 = (1,36), (2,18), (3,12), (4,9), (6,6), ...(앞의 값에 뒤집힘))

  고로 6까지만 검사하면 모든 순서쌍을 알수있음(대신 +2)

  단, (6,6) 처럼 제곱근일 경우는 1개이므로 -1을 수행

또한 값**0.5 == sqrt(값)이다.