codility 10-2. CountFactors

|

문제출처

문제

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.

Assume that: N is an integer within the range [1..2,147,483,647]. Complexity: expected worst-case time complexity is O(sqrt(N)); expected worst-case space complexity is O(1).

풀이코드

• 시간복잡도 : O(sqrt(N))
• 1 ~ 루트 N 까지의 숫자만 검색하여 시간복잡도 O(sqrt(N)) 으로 연산
def solution(N):
i = 1
result = 0
while i**2 <= N:
print(i)
if i ** 2 == N:
result += 1
elif N % i == 0:
result += 2
i += 1
return result


다른사람 코드

def solution(N):
candidate = 1
result = 0
while candidate * candidate < N:
# N has two factors: candidate and N // candidate
if N % candidate == 0:
result += 2

candidate += 1

# If N is square of some value.
if candidate * candidate == N:  result += 1

return result