[Swift 알고리즘] 프로그래머스(Lv.1) - 소수 찾기

안녕하세요. 개발 중인 정주입니다.

 

오늘은 프로그래머스 - 소수 찾기 문제를 풀었습니다.

 

---

목차

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

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

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

 

---

풀이

이 문제는 최대 수가 1000000으로 수가 꽤나 큽니다. 따라서 반복문을 1000000으로 하면 시간 초과가 나기 때문에 sqrt()를 사용하여 소수를 구해야 합니다.

 

저는 첫 번째로 일반적인 소수 구하는 방법으로 풀었고 두 번째로는 에라토스테네스의 체 방법을 이용해 풀었습니다.

 

sqrt()를 이용한 소수 공식

2부터 sqrt(n) 사이에 나누어 떨어지는 수가 있으면 소수가 아님을 이용한 방법입니다.

 

에라토스테네스의 체

에라토스테네스의 체는 에라토스테네스가 발견한 소수를 구하는 방식입니다.

자세한 내용은 링크로 대체합니다. https://ko.wikipedia.org/wiki/에라토스테네스의_체

 

속도 비교

첫 번째가 에라토스테네스의 체를 이용한 결과이고 두 번째가 일반 공식을 이용한 결과입니다.

효율성 테스트 결과를 보면 거의 10배 가까이 차이가 나는 것을 알 수 있습니다.

 

따라서 이 문제처럼 제한 수가 큰 경우에는 에라토스테네스의 체 방식을 이용해야 합니다.

 

---

전체 코드

import Foundation

func solution(_ n:Int) -> Int {
    var isPrime: [Bool] = Array(repeating: true, count: n+1)
    
    isPrime[0] = false
    isPrime[1] = false
    
    if n >= 4 {
        for i in 2...Int(sqrt(Double(n))) {
            for j in 2...n/i {
                isPrime[i * j] = false
            }
        }
    }
    
    let result = isPrime.filter { $0 }.count
    
    //let result = (1...n).filter { isPrime($0) }.count
    return result
}

func isPrime(_ n: Int) -> Bool {
    if n <= 3 {
        return n == 1 ? false : true
    } else {
        for i in (2...Int(sqrt(Double(n)))) {
            if n % i == 0 {
                return false
            }
        }

        return true
    }
}

let n = 5
print(solution(n))

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.