기존 약수구하기

N의 약수를 구한다면 단순하게

for i in range(1, n):
	if n%i == 0:
    	~~~

이런식으로 구할 수 있겠지만 O(N)의 시간복잡도이다. N이 엄청 크다면 그만큼 느릴것이다.

수정된 약수 구하기

1. N의 제곱근구하기
2. range(1, N의 제곱근)으로 제곱근까지의 약수들구하기
3. 제곱근까지의 약수들을 순회참조해서 N으로 나눈 몫을 약수에 추가

코드로 보면 이렇다.

from math import *
#n의 약수들을 set으로 반환
def getDivisor(n:int)->set:
    root = isqrt(n) #math의 반환형int인 함수로, 제곱근의 floor를 반환
    divisors = set() #만약 리스트로 아래 알고리즘을 실행하면 약수에 제곱근 2개가 똑같이 들어간다. 중복을 피하기 위해 set 사용
    for i in range(1, root+1):
        if n%i == 0:
            divisors.add(i)
    for divisor in divisors.copy():#순회탐색알 제곱근까지의 약수들과 추가당하는 제곱근까지의 약수들을 서로 구분하기 위해 copy사용
        divisors.add(n//divisor)
    return divisors

이는 O(루트N)의 시간복잡도를 가지니 더욱 빠르다.

참고문제

프로그래머스 : 약수의 개수 구하기