[Algorithm] 약수 구하기 a.k.a O(sqrt(n))

임의의 수 N에 대해 N의 약수들 중 $\sqrt{N}$ 이하인 약수로 $\sqrt{N}$ 이상인 약수를 구할 수 있다.

그러므로 N의 전체 약수를 찾기 위해 $O(N)$이 아닌 $O(\sqrt{N})$의 시간 복잡도를 갖을 수 있다.

수학적 증명 참고

# 약수 구하기
def get_primes(n : int) -> set: # list보다 set을 쓰는 이유 : 제곱 수의 중복 약수 처리를 위해 e.g. 16 = 4 x 4
    prime_list, i = {}, 1 
    
    while i**2 <= n: # i <= math.sqrt(n):
    	if n%i == 0:
            prime_list.add(n)
            prime_list.add(n/i)
        i+=1
        
    return prime_list

# 소수 판별하기
def is_prime(n : int) -> bool:
    if n <= 1: 
    	return False
    else: 
    	i = 2
    
    while i**2 <= n: # i <= math.sqrt(n):
    	if n%i == 0:
            return False
        
    return True