(BOJ) 1016 제곱 ㄴㄴ 수

1016 제곱 ㄴㄴ 수

• 분류 : 수학, 정수론, 소수 판정, 에라토스테네스의 체

문제

어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다.

제곱수는 정수의 제곱이다.

min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

입력

첫째 줄에 두 정수 min과 max가 주어진다.

출력

첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다.

제한

• 1 ≤ min ≤ 1,000,000,000,000
• min ≤ max ≤ min + 1,000,000

예제 입력 1

1 10

예제 출력 1

7

예제 입력 2

15 15

예제 출력 2

1

예제 입력 3

1 1000

예제 출력 3

608

Solution

펼쳐보기

import java.util.*


private var min: Long = 0
private var max: Long = 0

private lateinit var isPrime: BooleanArray

fun main() {
    input()
    init()
    solve()
}

private fun input() = with(Scanner(System.`in`)) {
    min = nextLong()
    max = nextLong()
}

private fun init() {
    val size = (max - min + 1).toInt()
    isPrime = BooleanArray(size) {
        false
    }
}

private fun solve() {
    var index = 2L
    while(index * index <= max) {
        val pow = index * index
        val start = if (min % pow == 0L) {
            min / pow
        } else {
            min / pow + 1
        }
        var i = start
        while (i * pow <= max) {
            isPrime[(i * pow - min).toInt()] = true
            i++
        }
        index++
    }

    val result = isPrime.count { !it }
    println(result)
}

Point of Thinking

• min과 max값을 입력받은 후, 두 값의 차만큼 배열을 초기화한다.
  • 여기서는 BooleanArray로 선언하여 이 배열의 인덱스가 제곱 ㄴㄴ 수, 값이 소수인지 아닌지 판정한다.
• 필요한 건 소수(prime number)이므로 index를 2부터 max까지 순회한다.
• pow 값을 계산할 때는 min에 대한 예외처리를 수행해야한다.
• 이후 max 범위 내에서 index의 제곱에 해당하는 인덱스를 전부 true로 바꾼다. (=에라토스테네스의 체)
• 순회 완료 후 true인 값을 카운트해서 출력하면 Accpeted.

References

• https://www.acmicpc.net/problem/1016