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

👆문제풀러 가기👆

문제 설명

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

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.

(1은 소수가 아닙니다.)

 

제한 조건

• n은 2이상 1,000,000이하의 자연수입니다.

 

입출력 예

n	result
10	4
5	3

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

---

풀이 [ 메모리: 16,793kb, 최대 시간: 1066.65.ms ]

import Foundation

func solution(_ n:Int) -> Int { 
    var result = 0
    
    for i in 2...n {
        if isPrimeNumber(i) {
            result += 1
        }
    }

    return result
}

func isPrimeNumber(_ num : Int) -> Bool {
    if num < 2 { return false }
    if num == 2 || num == 3 { return true }

    // 임의의 수를 제곱근까지 나누었을 때, 나누어 떨어지면 합성수.
    for i in 2...Int(sqrt(Double(num))) {
        if num % i == 0 {
            return false
        }
    }
    
    // 나누어떨어지지 않으면 소수
    return true
}

 

 임의의 수(n)에 대한 소수 구하는 법 

1. 1이상 n 미만의 모든 수로 n을 나눈 나머지가 0이 있는지 구하기
2. 1이상 n/2이하의 모든 수로 n을 나눈 나머지가 0이 있는지 구하기
3. 1이상 n 제곱근 이하의 모든 수로 n을 나눈 나머지가 0이 있는지 구하기

주로 이 3가지를 사용하는데, 당연하게도 3번이 가장 효율적이다.

소수를 구할 때 실질적 중간값은 n의 제곱근이기 때문.

 

그 외에도 에라토스테네스의 체 등이 있지만, 상황에 따라 비효율적일 수 있는 코드이기에 잘 사용하지 않았었다.

 

다만, 위의 코드는 범용적인 코드이지만 이 문제에 적합한 풀이라고 보기는 어렵다. .

시간초과를 간신히 넘겼기에 수면 위에 입만 둥둥 떠서 간신히 숨만 쉬는 수준.. 그래서 다른 사람의 풀이를 또 가져와봤다.

 

다른 풀이 [ 메모리: 16,793kb, 최대 시간: 246ms ]

func solution(_ n:Int) -> Int {
    var check = Array(repeating: 0, count: n + 1)
    var cnt = 0

    for i in 2...n {
        // 1. 이미 확인된 배열인지 확인 (= 소수일 때)
        if check[i] == 0 {
            // 2. 확인한 갯수 카운팅 (= 갯수 증가)
            cnt += 1
            
            // 3. i의 배수인 배열의 인덱스를 1로 수정 (= 합성수 제거)
            for j in stride(from: i, to: n + 1, by: i) {
                check[j] = 1
            }
        }
    }

    return cnt
}

전에는 뭐 이런 코드가 있나,, 싶어서 그냥 지나쳤었는데 이제는 이해가 됐다.

인덱스로 사용중인 'i'를 호출하면 소수 배열도 확인할 수 있다.

약 4배 정도의 효율 차이를 보일거라고는 생각 못했지만, 또 한 번 배워간다..

 

 시간 차가 발생하는 이유 

똑같이 for문을 2번 사용하는 n^2의 시간복잡도이지만, 

내 풀이는 약수가 나올 때까지 모든 수를 돌리는 방법이라면,

이 풀이는 조건을 통해 소수가 아닌 값을 미리 쳐내기 때문에 외부 for문 안에서 내부 for문이 돌아가는 상황 자체가 현저히 적다.

 

그리고 위에서 말한 "상황"에 따라 비효율적일 수 있는 이유는, 수가 커질수록 소수의 배수가 많아져 걸러지는 수가 많아지듯 

수가 크고 많을 때 적합한 코드이기 때문이었다.

 

이로써 소수의 배수를 제외한 나머지 수를 확인하는 방법(에라토스테네스의 체)이 소수 찾기의 4번째 방법이 되었다.

 

출처: 위키백과 - 에라토스테네스의 체