CountFactors

🔗 문제 링크

https://app.codility.com/programmers/lessons/10-prime_and_composite_numbers/count_factors/start/

❔ 문제 설명

A positive integer D is a factor of a positive integer N if there exists an integer M such that N = D * M.

For example, 6 is a factor of 24, because M = 4 satisfies the above condition (24 = 6 * 4).

Write a function:

def solution(N)

that, given a positive integer N, returns the number of its factors.

For example, given N = 24, the function should return 8, because 24 has 8 factors, namely 1, 2, 3, 4, 6, 8, 12, 24. There are no other factors of 24

⚠️ 제한사항

• N is an integer within the range [1..2,147,483,647].

💡 풀이 (언어 : Python)

처음에는 그냥 전체탐색으로 나누기 나머지가 0인 경우를 카운트하는 코드를 짰는데, 시간복잡도 $O(N)$인데 시간 초과가 나왔다. 시간복잡도를 줄이는게 포인트인 문제였다. 타인의 풀이를 봤더니 예전에 본적 있던 알고리즘이다. 새까맣게 까먹었다. 약수는 대칭적으로 나온다. 예를들어 12면 약수가 1, 2, 3, 4, 6, 12인데 왼쪽, 오른쪽 3개씩 대칭인 모양이 나온다. 짝끼리 곱하면 12가 된다. 다만 9같이 제곱근이 정수로 떨어지면 약수가 1, 3, 9로 중간에 자기 자신이 짝인 경우가 하나 생긴다. 그래서 이경우는 하나 빼주면 된다. 시간복잡도는 $O(sqrt(N))$

import math

def solution(N):
    count = 0
    # 제곱 수의 정수 범위까지만 탐색
    for n in range(1, int(math.sqrt(N))+1):
        # 약수인 경우
        if N % n == 0:
            # 자기 자신이 약수 짝인 경우 +1만 카운트
            if n ** 2 == N:
                count += 1
            else:
                count += 2

    return count