백준 - 제곱 ㄴㄴ 수 (1016)

let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
let (min, max) = (input[0], input[1])
var arr = Array(min...max)

for i in 2...max {
    let now = i * i
    if now > max {
        break
    }
    var j = min / now
    if min % now != 0 {
        j += 1
    }
    while now * j <= max {
        arr[(now * j) - min] = 0
        j += 1
    }
}

print(arr.count - arr.filter{ $0 == 0 }.count)

• 에라스토테네스의 채 원리를 이용하여 제곱 ㄴㄴ 수를 찾는다.
• 2부터 시작해서 제곱수를 찾고 min과 max 사이에 있는 제곱수의 배수를 모두 지운다.
  • min보다 크거나 같은 수부터 탐색하기 위해 min을 now로 나눠서 j의 값을 구한다. → 이때 min / now가 나누어 떨어지지 않는 경우에는 j값에 1을 더해주어야 한다.