[코딜리티] Lesson 10. Prime and composite numbers - CountFactors 문제 (+파이썬 코드)

Question. CountFactors

 

약수 개수 구하는 문제다.

---

Answer. O(sqrt(n))

​

i*i <= n 을 이용하면 sqrt(n) 만에 풀 수 있다.

​

i*i 다음에 등장하는 수는 앞에 이미 등장한 수와의 곱으로 표현되기 때문에 i*i까지만 조회하면 된다.

 

import math

def solution(N):
    ans = 0
    for i in range(1, int(math.sqrt(N))+1):
        if N % i == 0:
            if i*i == N:
                ans += 1
                break

            else:
                ans += 2
    
    return ans

 

 

 

Test results - Codility

 

sol 1)
Time Complexity	O(sqrt(n))
Space Complexity	O(1)