문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

두 개의 정수 left와 right가 주어졌을 때, [left, right] 범위 내에 있는 숫자들 중에서 이진 표현에서 설정된 비트수가 소수인 숫자의 개수를 반환해라.

정수가 가지는 비트 수는 이진수로 표현했을 때 1의 개수와 같다는 것을 기억해라.

• 예를 들면, 21을 이진수로 작성하면 1010이 되는데, 3개의 비트가 성절되어 있음을 의미한다.

Example

#1
Input: left = 6, right = 10
Output: 4
Explanation:
6 -> 110 (2개의 비트가 설정되어있고, 2는 소수이다)
7 -> 111 (3개의 비트가 설정되어있고, 3은 소수이다)
8 -> 1000 (1개의 비트가 설정되어있고, 1은 소수가 아니다)
9 -> 1001 (2개의 비트가 설정되어있고, 2는 소수이다)
10 -> 1010 (2개의 비트가 설정되어있고, 2는 소수이다)
4개의 숫자가 설정된 비트 수가 소수이다.

#2
Input: left = 10, right = 15
Output: 5
Explanation:
10 -> 1010 (2개의 비트가 설정되어있고, 2는 소수이다)
11 -> 1011 (3개의 비트가 설정되어있고, 3은 소수이다)
12 -> 1100 (2개의 비트가 설정되어있고, 2는 소수이다)
13 -> 1101 (3개의 비트가 설정되어있고, 3은 소수이다)
14 -> 1110 (3개의 비트가 설정되어있고, 3은 소수이다)
15 -> 1111 (4개의 비트가 설정되어있고, 4는 소수가 아니다)
5개의 숫자가 설정된 비트수가 소수이다.

Constraints

• 1 <= left <= right <= 10^6
• 0 <= right -left <= 10^4

Solved

class Solution {
    public int countPrimeSetBits(int left, int right) {
        int result = 0;

        for(int i = left; i <= right; i++){
            int bitCount = Integer.bitCount(i);

            if(isPrime(bitCount)){
                result++;
            }
        }

        return result;
    }

    private boolean isPrime(int bitCount){
        if(bitCount <= 1){
            return false;
        }

        for(int i = 2; i * i <= bitCount; i++){
            if(bitCount % i == 0){
                return false;
            }
        }

        return true;
    }
}