[백준/BOJ] 1124번: 언더프라임

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

1124번: 언더프라임

문제

자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다.

어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, 그 수를 언더프라임 이라고 한다. 12는 목록에 포함된 소수의 개수가 3개이고, 3은 소수이니 12는 언더프라임이다.

두 정수 A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 정수 중에서 언더프라임인 것의 개수를 구해보자.

입력

첫째 줄에 두 정수 A와 B가 주어진다.

출력

첫째 줄에 A보다 크거나 같고, B보다 작거나 같은 언더프라임 개수를 출력한다.

해설

에라토스테네스의 채를 이용하여 b까지의 소수를 구한다.

특정 수가 소수라면 그 수의 배수들을 소수가 아니라고 처리해주는데, 이 과정에서 배수가 소수로 몇 번 나누어 떨어지는지를 확인해준다.(소인수분해를 하면 소수들의 곱셈으로 이루어지기 때문이다.)

 

이를 마쳤다면 a부터 b까지의 수 중에서 소수인지를 체크한 배열을 통해

소인수분해를 했을 때 수의 개수가 소수인 개수를 세면 된다.

소스 코드

fun main() = with(System.`in`.bufferedReader()) {
    val (a, b) = readLine().split(" ").map { it.toInt() }
    val prime = IntArray(b + 1) { 1 }
    val check = IntArray(b + 1) { 1 }
    prime[0] = 0; prime[1] = 0
    for(i in 2 .. b) {
        if(prime[i] > 0) {
            for(j in 2 * i .. b step i) {
                prime[j] = 0
                var temp = j
                while(temp % i == 0) {
                    temp /= i
                    check[j]++
                }
            }
        }
    }
    var underPrime = 0
    for(i in a .. b) {
        if(prime[check[i] - 1] > 0) underPrime++
    }
    println(underPrime)
}