[Swift 알고리즘] Programmers 소수 찾기

Level 1 연습문제

소수 찾기

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

 

입출력 예

print(solution(10)) //4
print(solution(5)) //3

 

1차 시도 - 43.8점

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

정말 원시적인 방법으로 그냥 단순하게 2부터 n까지 약수가 본인 하나뿐인 것들을 일일이 찾아보았다. 비효율적이긴 하지.

결과는 끔찍하고만.. 

 

2차 시도 - 50점

func solution(_ n:Int) -> Int {
    if n == 2 { return 1 }
    var result = 1
    for i in 3...n {
        if !(i%2 == 0) && (2...i).filter{ i%$0 == 0 }.count == 1 {
            result += 1
        }
    }
    return result
}

2의 배수는 탐구하지 말자 생각하고 해줬지만 그래도 시간초과..

 

아 이러면 소수를 찾는 다른 공식이나 방법이 있겠다 싶어 찾아보다 에라토스테네스의 체 라는것을 발견.

에라토스테네스의 체 : 

 

3차시도 - 56.3점

func solution(_ n:Int) -> Int {
    var arr = Array(2...n)
    var result = 0
    for i in 2...n {
        if arr.contains(i) {
            result += 1
            arr = arr.filter{!($0%i == 0)}
        }
    }
    return result
}

2...n까지 배열을 만들어준 후, i에서 n까지 수 중에 해당 수 가 배열에 남아있다면, +1을 하고 i의 배수들을 배열에서 삭제하도록(배수가 아닌것만 배열에 남기도록) 해주었다. 계속 for문 돌리는 것 보다 훨씬 효율적이라고 생각했는데 

하지만 결과는 여전히...

실패는 했지만 그래도 실행시간은 점점 빨라지고있다.. 힘을내..!

 

4차 시도 - 56.3점

func solution(_ n:Int) -> Int {
    var arr = Array(repeating: 0, count: n+1)
    var result = 0
    for i in 2...n {
        if arr[i] == 0 {
            for j in i...n {
                if j*i <= n {
                    arr[j*i] = 1
                }
            }
            result += 1
        }
    }
    return result
}

에라토스테네스의 체를 이용하여, 숫자 배열 대신 0으로만 이루어진 배열을 만들고, index 값으로 배수들을 1로 만들어버리는 방법이다.

(다른 분의 C++ 통과 코드를 참고해서 해봤는데 이게 아닌가..? 아니면 swift랑 다른가..?)

아 그리고 그냥 호기심에 같은 코드로 0, 1 대신 true, false 이용해서 해봤는데 시간은 비슷했다. 0, 1이 미세하게 더 빨랐움

 

통과 답안...

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

아.. 어쩔 수 없이 타인의 답지를 참고해버렸다.. 내 능력 밖이었어.. ㅠ 

for stride 구문을 이용해서 배수들을 없애야 했나보다. 처음보는 친구다.. 아직 모르는게 참 많다

for ? in stride(from: _, through: _, by: _) : from 부터 by 씩 through 까지