[프로그래머스 LV.0] 소인수분해

소인수분해

문제 설명

소인수분해란 어떤 수를 소수들의 곱으로 표현하는 것입니다. 예를 들어 12를 소인수 분해하면 2 * 2 * 3으로 나타낼 수 있습니다. 따라서 12의 소인수는 2와 3입니다. 자연수 n이 매개변수로 주어질 때 n의 소인수를 오름차순으로 담은 배열을 return 하도록 solution 함수를 완성해 주세요.

제한 사항

• 2 ≤ n ≤ 10,000

입출력 예

n	result
12	[2, 3]
17	[17]
420	[2, 3, 5, 7]

입출력 예 설명

입출력 예 #1

• 12를 소인수분해하면 2 * 2 * 3입니다. 따라서 [2, 3]을 return 합니다.

입출력 예 #2

• 17은 소수입니다. 따라서 [17]을 return 해야 합니다.

입출력 예 #3

• 420을 소인수분해하면 2 * 2 * 3 * 5 * 7입니다. 따라서 [2, 3, 5, 7]을 return 합니다.

---

제출

import Foundation

func solution(_ n:Int) -> [Int] {
    var arr = Array(repeating: true, count: n+1)
    var primes = [Int]()
    
    for i in 2...n {
        if arr[i] == true {
            for j in stride(from: i, through: n, by: i) {
                    arr[j] = false
            }
            primes.append(i)
        }
    }
    return primes.contains(n) ? [n] : primes.filter{n%$0 == 0}
}

소수인지 판별하기 위한 배열 arr와 소수를 담을 배열 primes를 선언한다.
i를 2부터 n까지 1씩 증가시키면서, arr[i]가 true라면 i의 배수들의 arr 값을 false로 바꾼 후 primes 배열에 i를 추가한다

이후 primes 함수의 n 이 있다면, n이 소수이기 때문에 n을 배열에 넣어 반환한다
primes 함수에 n이 없다면, filter 함수를 사용하여 n을 나눈 나머지가 0인 값들을 반환한다