Lesson 10: Prime and composite numbers → Count Factors

문제

CountFactors coding task - Learn to Code - Codility

---

문제 풀이

예를 들어 24라는 수가 주어지면 24의 약수의 개수를 효율적으로 구하는 문제이다. 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24로 개수는 8개 이다.

 

---

코드

def solution(N):
    i = 1
    ret = 0
    while i * i < N:
        if N % i == 0:
            ret += 2
        i += 1

    return ret + 1 if i * i == N else ret

• 브루트포스로 풀면 효율성 부분을 통과할 수 없다.
• 약수는 구하고자 하는 수인 N 까지 모두 탐색하지 않아도 되는 특성을 활용하면 쉽게 풀 수 있다.