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
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
app.codility.com
| sol 1) | |
| Time Complexity | O(sqrt(n)) |
| Space Complexity | O(1) |
728x90
'Problem Solving > Codility' 카테고리의 다른 글
| [코딜리티] Lesson 10. Prime and composite numbers - CountFactors 문제 (+파이썬 코드) (0) | 2021.02.21 |
|---|
댓글0