백준 - 신기한 소수 (2023)

import Foundation

let N = Int(readLine()!)!
var answer = ""

dfs(2, 1)
dfs(3, 1)
dfs(5, 1)
dfs(7, 1)

print(answer)

func dfs(_ number: Int, _ digit: Int) {
    if digit == N {
        if isPrime(Double(number)) {
            answer += "\(number)\n"
            return
        }
    }
    for i in stride(from: 1, to: 10, by: 2) {
        let nextNumber = number * 10 + i
        if isPrime(Double(nextNumber)) {
            dfs(nextNumber, digit + 1)
        }
    }
}

func isPrime(_ number: Double) -> Bool {
    if [2, 3, 5, 7].contains(number) { return true }
    
    let end = Int(number.squareRoot()) + 1
    return (2...end).filter{ Int(number) % $0 == 0 }.isEmpty
}

• DFS의 형태로 자릿수를 하나씩 더해가며 소수인지 여부를 검사한다.
  • 처음에는 2, 3, 5, 7, 중간부터는 홀수만을 탐색하기 때문에 시간 복잡도를 줄일 수 있다.
• 소수 판별을 위해 filter 메소드를 썼더니 한 자리 수(2, 3, 5, 7)은 제대로 판별이 되지 않는다. 그래서 꾸역꾸역 한 자리 수는 따로 검사하는 코드를 추가했다.