백준 - 거의 소수 (1456)

import Foundation

let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
let (A, B) = (input[0], input[1])
var numbers = Array(repeating: true, count: Int(Double(B).squareRoot())+1)
(numbers[0], numbers[1]) = (false, false)

var prime = [Int]()
var answer = 0

// 소수 구하기
for i in stride(from: 2, to: numbers.count, by: 1) {
    let now = numbers[i]
    if now == false {
        continue
    }
    prime.append(i)

    for j in stride(from: i + i, to: numbers.count, by: i) {
        numbers[j] = false
    }
}

// 구한 소수로 거의 소수 구하기
for num in prime {
    var now = num
    while Double(num) <= Double(B) / Double(now) {
        if Double(A) / Double(now) <= Double(num) {
            answer += 1
        }
        now *= num
    }
}

print(answer)

• A와 B 사이에 있는 모든 소수를 구한 다음 그 소수들을 이용해서 A와 B 사이에 있는 거의 소수를 찾는다.

→ 아이디어 자체는 간단하지만 오버플로우를 신경써야 하는 점이 조금 까다로웠다.

• B의 최대값은 10^14인데, 크기가 10^14인 배열은 만들 수 없다.
  • 따라서 B의 제곱근까지만 담을 수 있는 배열을 선언해서 B의 제곱근보다 작거나 같은 소수만 찾아준다.
  • B의 제곱근보다 큰 소수로는 B보다 작거나 같은 거의 소수를 만들 수 없기 때문에 정답에도 영향이 없다.
• 거의 소수를 구할 때 N제곱을 하다보면 오버플로우가 발생할 수 있다.
  • N^K과 A, B가 아니라 N과 A / N^K-1, B / N^K-1을 비교해서 오버플로우를 방지한다.
  • 결과값이 정확하게 계산될 수 있게 Double형으로 변환하여 계산한다.