[Programmers] [Lv.1] [Swift] 소수 찾기

문제

소수 찾기

문제파악하기

• 에라토스테네스의 체를 이용하면 마치 체에 거르듯 효율적인 코드를 짤 수 있다.
• 2를 구한순간부터 2의 제곱은 모두 소수가 아니게 된다.
• 다른 수도 마찬가지로 제곱근까지만 소수인지 판별한다면 나머지 수는 셀 필요가 없기 때문이다.

풀이

func isPrime(_ n:Int) -> Bool {
    var i = 2
    while i * i <= n { // i의 제곱이 n보다 작거나 같을 때
        if n % i == 0 { // n이 한번이라도 i로 나누어 떨어지면
            return false // 소수가 아니다
        }
        i += 1 // 다음 수 체크
    }
    return true // 모든 수를 체크했을 때 소수임
}

func solution(_ n:Int) -> Int {
    var cnt = 0
    if n == 1 { return 0 } // 예외1
    if n == 2 { return 1 } // 예외2
    for i in 2...n { // 0과 1은 소수가 아니니 셀 필요 없음
        if isPrime(i) { // i가 소수라면
            cnt += 1 // 카운트
        }
    }
    return cnt
}

🤔 FEEDBACK

• 전에 풀었던 문제인데도 에라토스테네스의 체 개념이 흐릿해져있었다.
• 같은 문제라도 복습을 해야할 필요성을 느낀다.
• 효율성 이게 맞나 ...
  

다른 풀이

func solution(_ n:Int) -> Int {
    var isPrime: [Bool] = [Bool](repeating: true, count: n)
    var count: Int = 0

    guard 3 < n else {
        return n - 1
    }

    //  1은 소수가 아니다
    isPrime[0] = false

    //  2를 제외한 2의 배수는 소수가 아니다
    count += 1
    for i in 2...n / 2 {
        isPrime[i * 2 - 1] = false
    }

    for i in stride(from: 3, through: n, by: 2) {
        var j = i

        //  이미 소수가 아닌 것으로 판정된 경우에는 더 볼 필요 없다
        guard isPrime[j - 1] else {
            continue
        }

        while (j <= n) {
            if j == i {
                isPrime[j - 1] = true
                count += 1
            } else {
                isPrime[j - 1] = false
            }

            j += i * 2
        }
    }

    return count
}

• 이 엄청난 효율성은 도대체 뭐지...
• 난.. 에라토스테네스의 체를 도대체 왜 공부한거지?
• 내 머리가 나쁨을 실시간으로 보니 실감이 안나네..