[Swift 코테 기초] 제곱근으로 약수 구하기

 

1. 약수 구하기

- N을 1부터 N까지의 수로 나눠서 그 값이 0이 되면 나눈 수는 N의 약수이다. 하지만 이 방법은 매우 비효율적이다.

- N의 약수는 N의 제곱근보다 클 수 없기 때문에 범위를 N/2로 한다.

    - 주어진 수의 제곱근을 넘어선 약수는 이미 이전에 발견한 약수와 곱하여 나타낼 수 있기 때문 

    - 범위가 N/2이기 때문에 리턴 배열에 N이 포함되지 않으므로 추가해준다.

    ex) 36의 경우 6까지만 탐색한다. 6 이상의 숫자는 이미 이전에 발견한 약수와의 곱으로 표현할 수 있다. (12 * 3, 3 * 12)

func solution(_ n: Int) -> [Int]{
    return Array(1...n/2).filter { n % $0 == 0 } + [n]
}

print(solution(10))    //[1, 2, 5, 10]

 

 

2. 최소공배수 구하기 - 유클리드 호제법

//최대공약수 greatest common divisor
//a > b
func gcd(_ a: Int, _ b: Int) -> Int {
	if b == 0 { return a }
    else { return gcd(b, a % b) }
}


//축약
func gcd(_ a: Int, _ b: Int) -> Int {
	return b == 0 ? a: gcd(b, a % b)
}

 

 

3. 최대공약수 구하기 - ab = 최대공약수 * 최소공배수

//최소공배수 - least common multiple
//ab = 최소공배수 * 최대공배수 => 최소공배수 = ab / 최대공배수
func lcm(_ a: Int, _ b: Int) -> Int {
	return a * b / gcd(a, b)
}