Swift) 백준 1929번 (소수구하기)

요구능력 : 에라토스테네스의 체 알고리즘을 사용할 수 있느냐

 

코드설명 : 

에라토스테네스의 체를 사용했다.

M부터 N까지 이지만, 배열은 2부터 생성해주고 배수 지워줄 때도 2부터 지워줬는데

그 이유는 한번 M부터 N으로 실행해서 출력해보면 알 수 있을 것이다.

 

후기 : 갓빈나님의 동영상을 보고 학습했는데 바로 이해가 되버렸다.( https://www.youtube.com/watch?v=5ypkoEgFdH8&t=498s)

문제풀어 볼 생각도 안하고 바로 에라토스테네스의 체라는 알고리즘을 찾아봤는데,

그 이유는 솔직히 천재가 아닌이상 "무슨알고리즘을 써라" 라는 식의 문제를 혼자서 풀수없다.

수학에서 근의공식을 쓰는거처럼..

오기가 있으신분들도 억지부리지말고 학습하고 이해한다음 풀어보시길

---

let getMN = readLine()!.split(separator: " ").map{Int($0)! }
let M = getMN[0]
let N = getMN[1]

var arr: [Int] = Array(repeating: 0, count: N + 1)
for i in 2...N {
    arr[i] = i
}

for j in 2...N {
    if arr[j] == 0 {continue}
    for k in stride(from: j + j, through: N, by: j) {
        arr[k] = 0
    }
}

for w in M...N {
    if arr[w] != 0 {
        print("\(arr[w])")
    }
}