[백준 2023] 신기한 소수 (Swift)

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

 

 

소수

N (1~8사이의 정수)가 주어지면 N자리 수 중 신기한 소수 조건을 만족하는 수를 모두 출력하는 문제

신기한 소수 조건 : prefix 모든 접두어(?..수?)가 소수인 수

예) 7331 : 7도 소수, 73도 소수, 733도 소수, 7331도 소수

 

접근방법

1) 에라토스테네스의 체를 사용해서 N자리 수까지의 모든 수의 소수 여부를 저장한 배열을 만든 뒤, N자리 수를 하나씩 살펴보면서 그게 신기한 소수 조건을 만족하는지 확인한다 -> 시간초과

2) 에라토스테네스의 체로 소수 여부를 저장한 배열을 만든 뒤, N자리 수를 하나씩 살펴보는데, 이때 접두어가 소수가 아니면 그 접두어로 시작하는 수는 건너뛰기 -> 시간초과

3) 에라토스테네스의 체를 사용하지 않고, N자리 수를 하나씩 살펴보는데, 이때 접두어가 소수가 아니면 그 접두어로 시작하는 수는 건너뛰기 (소수를 확인하는 방법은 별도의 함수로 만들어 사용, 2부터 num의 제곱근까지의 숫자로 num을 나눠가면서 나누어 떨어지는 경우가 생기면 소수 X) -> 통과

 

소스코드

import Foundation

func isPrime(_ num:Int) -> Bool {
    if num == 2 {
        return true
    } else if num < 2 {
        return false
    } else {
        for d in 2...max(2,Int(pow(Double(num), 0.5))) {
            if num % d == 0 {
                return false
            }
        }
    }
    return true
}

func solution() -> [Int] {
    var result:[Int] = []
    // input
    let N:Int = Int(readLine()!)!
    
    // process : 완벽한 수
    let start = Int(pow(10.0, Double(N-1)))
    let end = Int(pow(10.0, Double(N)))

    var num = start
    while num < end {
        // 접두어 검사
        var isPerfect = true
        for m in (0..<N).reversed() {
            let d = Int(pow(10.0, Double(m)))
            let prenum = num/d
            if !isPrime(prenum) {
                num += d
                isPerfect = false
                break
            }
        }
        if isPerfect {
            result.append(num)
            num += 1
        }
    }
    
    return result
}

solution().forEach { print($0) }

 

에라토스테네스의 체 버전 소스코드

import Foundation

func solution() -> [Int] {
    var isPrime:[Bool] = Array<Bool>(repeating: true, count: 100000000)
    isPrime[1] = false
    var result:[Int] = []
    // input
    let N:Int = Int(readLine()!)!
    
    // process : 에라토스테네스의 체
    let start = Int(pow(10.0, Double(N-1)))
    let end = Int(pow(10.0, Double(N)))
    for i in 2...Int(pow(Double(end), 0.5)) {
        var d = i+i
        while d < end {
            isPrime[d] = false
            d += i
        }
    }
    
    // process : 완벽한 수
    var num = start
    while num < end {
        // 접두어 검사
        var isPerfect = true
        for m in (0..<N).reversed() {
            let d = Int(pow(10.0, Double(m)))
            let prenum = num/d
            if !isPrime[prenum] {
                num += d
                isPerfect = false
                break
            }
        }
        if isPerfect {
            result.append(num)
            num += 1
        }
    }
    
    return result
}

solution().forEach { print($0) }