[Swift] 소수 찾기

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건
n은 2이상 1000000이하의 자연수입니다.

Example

Input: 10
Output: 4
Explanation: 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

Input: 5
Output: 3
Explanation: 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

풀러가기

문제 이해

• 1과 자기자신, 2개뿐이다.

코드

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

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

풀이

• 어떤 정수가 소수인지 판별하는 방법은 그 소수의 제곱근까지 나누어 보는 것

  i * i <= n
  

• 여기가 효율성의 핵심이다.
• if == 1 은 발생하지 않지만 제약조건을 꼼꼼히 읽어보지 못했다.

다른 분의 멋진 코드

func solution(_ n:Int) -> Int {
    var primes:[Bool] = [Bool](repeating:false, count:n+1);
    var count = 0;
    for i in 2...n {
        if(!primes[i]){
            count = count + 1;
        }
        for j in 1...(n/i) {
            primes[i*j]=true;
        }
    }
    return count;
}

잘 배웠습니다.

재귀를 사용하지 않고 풀고 싶었는데 멋진코드는 성공했다. dp 를 사용해 공간 사용이 크지만 소수 문제는 dp로 접근하는 것이 좋을 것 같다.