[LeetCode/Easy] 762. Prime Number of Set Bits in Binary Representation

1. Input

1) 정수 left

2) 정수 right

 

2. Output

1) [left, right] 범위의 정수 중 2진수로 바꿨을 때 1의 개수가 소수인 수의 개수

 

3. Constraint

1) 1 <= left <= right <= 10^6

2) 0 <= right - left <= 10^4

 

4. Example

Input: left = 10, right = 15 -> Output: 5

설명:

10 -> 1010 -> 1이 2개 -> 2는 소수(O)

11 -> 1011 -> 1이 3개 -> 3는 소수(O)

12 -> 1100 -> 1이 2개 -> 2는 소수(O)

13 -> 1101 -> 1이 3개 -> 3는 소수(O)

14 -> 1110 -> 1이 3개 -> 3는 소수(O)

15 -> 1111 -> 1이 4개 -> 4는 합성수(X)

따라서 5를 반환한다.

 

5. Code

1) 첫 코드(2022/06/29)

int count = 0;
for(int i=left ; i<=right ; i++){
    int n = i;
    int d = 0;
    while(n>=1){
        d += n%2;
        n /= 2;
    }
    if(isPrime(d))
        count++;
} // for i

return count;

// 소수 판별 메서드
boolean isPrime(int d){
    if(d==1) return false;
    if(d==2) return true;

    for(int i=d-1 ; i>=2 ; i--)
        if(d%i==0) return false;

    return true;
}