[백준 스위프트] 6219번 소수의 자격

아이디어

에라토스테네스의 체를 이용하여 num(4000000)까지 소수를 생성하고 A와 B 사이에서만 소수를 찾은 다음 D와 소수를 String으로 만들어 contains 함수를 이용하여 요소로 가지고 있는지를 탐색하였다. 이때, A와 B에서 에라토스테네스의 체를 생성하려고 할 수 있는데 에라토스테네스의 체는 특정 구간에서부터가 아니라 2부터 순서대로 해야 하는 방식이라 그런 방식은 통하지 않는다.

 

해답

import Foundation

let input = readLine()!.components(separatedBy: " ").map { Int(String($0))! }
let A = input[0]
let B = input[1]
let D = input[2]
var cnt = 0
var num = 4_000_000
var numArray = Array(repeating: 0, count: num + 1)

for i in 2...num {
    numArray[i] = i
}

for i in 2...num {
    if numArray[i] == 0 {
        continue
    }
    for j in stride(from: i*i, through: num, by: i) {
        numArray[j] = 0;
    }
}
for i in A...B {
    if numArray[i] != 0 {
        if String(i).contains(String(D)) {
            cnt += 1
        }
    }
}
print(cnt)