프로그래머스 - 소수 찾기 [Swift]

소수 찾는 건 이번에 푼 것까지 한 10번째 풀어보는 것 같다.

소수 찾는 방식은 가장 비효율적인 2부터 n까지 전부 탐색하는 방법과

에라토스 테네스의 체, 그리고 내가 적용한 n의 루트(sqrt)까지만 검색하는 법까지 총 세 가지 방법이 있다.

그런데 예전에 에라토스 테네스의 체로 풀다가 오히려 시간 초과가 돼서 (아마도 내가 잘못했을 확률이 크지만 아무튼)

세 번째 방법, 그러니까 n의 sqrt값까지만 조사하는 방법을 선택했다.

 

여기 써 있는 isPrime함수는 꼭 머릿 속에 넣어 놓자.

 

정답코드:

func isPrime(_ number: Int) -> Bool {
    var i = 3
    if number == 2 {
        return true
    }
    if number % 2 == 0 {
        return false
    }
    while (i * i <= number) {
        if (number % i == 0) {
            return false
        }
        i += 2
    }
    return true
}

func solution(_ n:Int) -> Int {
    var count: Int = 1 // 2는 기본적으로 들어감.
    
    for i in 2...n where i % 2 != 0 {
        if isPrime(i) == true {
            count += 1
        }
    }
    return count
}

 

 

아마도 2~n까지 sqrt 개념을 적용하지 않고 전수조사하는 경우 효율성에서 fail을 받을 것이다.