프로그래머스 소수 찾기 Swift

Youtube

 

제가 직접 제작한 영상입니다!

 

영상으로 보시면 이해하시기 훨씬 수월하실거에요!!

 

---

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

n	result
10	4
5	3

---

풀이: 1빼고 즉 2부터 n까지 중 차례대로 i를 대입하고 i중에 1하고 자기 자신 제외한 다른 걸로 나눠지면 continue 바깥쪽 Loop를 하게 했다. 이렇게 했더니 만약 1부터 10000까지라면 10000번을 반복하는 것이다. 이것은 아주 효율성이 없을 뿐더러 시간초과가 난다.

솔루션 2

func solution2(_ n:Int) -> Int {
    var total = 0
    Loop :for i in 2...n {
        for j in 2...i{
            if i%j == 0 && j != i{
               continue Loop
            }
            }
        total += 1
        }
    return total
}

이런 식으로 풀어야하는데

에라토스테네스의 체라는 알고리즘으로 풀어야 한다.

방법은 우선 Array의 크기를 미리 정해준 뒤 안에다가 전부 false를 집어넣는다. n+1로 하는 이유는 배열이 0부터 시작하기 때문이다.

그렇게 한 뒤 1빼고 2부터 n까지 중 false인 값이 있다면 카운트를 +1해준 뒤 i의 배수를 모두 true로 바꿔준다.

한번에 차례대로 소수의 배수를 true로 해주기 때문에 시간을 크게 줄일 수 있다.

이렇게 차례차례 소수들의 배수를 체로 걸러내는 방법이 에라토스테네스의 체라는 것이다.

배수를 한 번에 없애는 방법이 바로 for stride구문인데 from은 ~부터 through는 ~까지 by는 ~씩 고로 소수부터 n까지 소수의 배수만큼 모두 트루로 바꿔줘라는 거다.

---

솔루션 1

func solution1(_ n: Int) -> Int {
    var count = 0
    var array = Array.init(repeating: false, count: n+1)
    
    for i in 2...n {
        if array[i] == false {
            count += 1
            
            for j in stride(from: i, through: n, by: i) {
               array[j] = true
            }
        }
    }
    return count
}
 

시간 비교 10000을 대입했을 때

에라토스 테네스의 체로 푼 솔루션 1은 0.2초가 걸리는 반면

그냥 노가다 형식으로 쓴 솔루션 2는 3초가 걸린다.

 

10만을 대입했을 경우

솔루션 1은 2초

솔루션 2는 264초가 걸린다.