백준 1929 - Swift

백준 1929 - Swift

 

https://www.acmicpc.net/problem/1929

 

이전 DFS에서 소수 찾는 함수에서 생각나서

문제 풀러 갔는데 이미 자바로 풀어져 있더라구요.

그래서 이번에 Swift로 갱신 +  에라토스테네의 체 원리 해서 다시 풀었습니다!

 

에라토스테네의 체 원리?

구하고자 하는 소수의 범위만큼 배열을 생성한 다음 2부터 현재 선택된 숫자의 배수에 해당하는

수를 배열에서 모두 제거하면서 찾는 방법

O(nlog(nlogn))으로 시간 복잡도가 굉장히 낮은 편!

 

 

코드

let input = readLine()!.split(separator: " ").map { Int($0)! }

let m = input[0]
let n = input[1]
var array = Array(repeating: 1, count: n + 1) // 1부터 n까지의 배열 생성 (값이 인덱스 요소와 동일하도록)

let max = Int(Double(n).squareRoot()) + 1

// i는 2부터 (1은 소수가 아니니까)
for i in 2...max { // 2부터 입력받은 수의 제곱근까지
    // 0은 소수가 이닌 수로써 체크 된 수
    if array[i] == 0 { continue } // 0이면 패스
    // i의 배수들을 소수가 아니라고 표시
    for j in stride(from: i*i, to: n+1, by: i) {
        // 숫자의 제곱부터 array의 zmrldls n까지 배수씩 증가하면서
        // i * i = i의 배수 처리시, i의 제곱보다 작은 배수들은 모두 이전 단계에서 처리되기 때문
        array[j] = 0
    }
}
 
// m ~ n 사이의 숫자 출력하기
for i in m...n {
    if i >= 2 && array[i] != 0 { // 숫자 1에 대한 처리해주기
        print(i)
    }
}

 

 

여기서 n의 제곱근까지만 확인하면 되는 이유는?

 

 

 

2년전에는 자바를 했었구나 싶었다는..

지금은 기억이 하나도 안 나거든요..

 

어쨌든 에라토스테네의 체 원리를 사용하니까 시간이 훨씬 줄었다!