[swift] 백준 - 1929번: 소수 구하기

1929번: 소수 구하기

문제 푸는 데 있어 도움이 되도록 나의 풀이와 개선된 풀이를 올립니다.
또한 풀이 후 다른 사람의 풀이를 보고 참고할만한 풀이도 올립니다.
- 문제에 따라 나의 풀이만 있을 수 있습니다.
- 해당 풀이들은 풀이 중 하나일 뿐 최선의 풀이는 아닐 수 있습니다.

 

---

 

문제 설명

 

- 여러개의 소수를 한번에 판별할 때는
에라토스테네스의 체를 사용하는게
시간복잡도 면에서 효율적입니다.

 

---

 

나의 풀이

let MN = readLine()!.split(separator: " ").map { Int($0)! }
var arr = Array(0...MN[1])
var result = ""
for i in arr {
    if i == 0 || i == 1 { arr[i] = 0; continue }
    for j in stride(from: i * 2, through: MN[1], by: i) {
        arr[j] = 0
    }
}
for i in MN[0]...MN[1] {
    if arr[i] != 0 { result += "\(arr[i])\n"}
}
print(result)

 

- 약 200ms의 시간의 걸림

 

---

 

참고할만한 풀이

let MN = readLine()!.split(separator: " ").map { Int($0)! }
var arr = [Bool](repeating: true, count: 1000001)
var result = ""
arr[1] = false
for i in 2...1000 where arr[i] == true {
    for j in 2...1000000/i {
        arr[i*j] = false
    }
}

for i in MN[0]...MN[1] {
    if arr[i] {
        result += "\(i)\n"
    }
}
print(result)

 

- 시간복잡도 면에서 좀 더 유리한 코드 (약 40ms)

 

---