[프로그래머스][Lv. 1] 소수 찾기 Swift 풀이

https://programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기

풀이

 

입력으로 주어진 정수 n 부터 1까지의 수 중 소수의 갯수를 반환하는 문제이다.

CS를 전공한다면 누구나 알고리즘 강의에서 한번씩은 배우고 지나가는 '에라토스테네스의 체'를 활용하면 소수 판별이 가능하다.

(참고 : 위키백과_에라토스테네스의 체)

 

끝!

import Foundation
 
var arr = [Bool]()
 
func eratosthenes(_ num: Int) {
    let sqrtNum: Int = Int(sqrt(Double(num))) + 1
    for i in 2...sqrtNum {
        for j in 1...arr.count/i {
            if j == 1 {
                continue
            }
            arr[i * j - 1] = false
        }
    }
}
 
func solution(_ n:Int) -> Int {
    arr = [Bool](repeating: true, count: n)
    arr[0] = false
    eratosthenes(n)
    var cnt = 0
    for num in arr {
        cnt += (num == true ? 1 : 0)
    }
    return cnt
}