본문 바로가기
Problem Solving/Codility

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

by sohyunwriter 2021. 2. 21.

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

댓글0