(C++) - LeetCode (easy) 762. Prime Number of Set Bits in Binary Representation

https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/description/

Prime Number of Set Bits in Binary Representation - LeetCode

bit masking과 소수판별 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

생성자에서 prime 여부를 판별할 수 있는 vector primeCheck를 선언 후 소수인지 여부를 저장해줍니다.

📔 풀이과정

1. 함수 getSetBits를 수행해 10진수인 num을 인자로 받아 2진수로 바꾼 결과에 대해 1의 개수를 세줍니다.2. left ~ right까지 loop를 돌며 bits의 개수를 세준 후 isPrime함수를 수행해 primeCheck가 1인지 여부를 확인해줍니다.3. 센 결과를 ans에 반영해줍니다.

📔 정답 출력 | 반환

ans를 반환합니다.

---

📕 Code

📔 C++

class Solution {
public:
    vector <int> primeCheck;

    Solution(){
        primeCheck.resize(1000001,1);
        primeCheck[1] = 0;
        for(int i = 2; i * i <= 1000000; i++) {
            if(!primeCheck[i]) continue;
            for(int j = i + i; j <= 1000000; j += i) primeCheck[j] = 0;
        }
    }

    int getSetBits(int num){
        int bits=0;
        while(num) {
            if(num & 1) bits++;
            num >>= 1;
        }
        return bits;
    }

    bool isPrime(int num) {
        return primeCheck[num];
    }

    int countPrimeSetBits(int left, int right) {
        int ans=0;
        for(int i = left; i <= right; i++) {
            if(isPrime(getSetBits(i))) {
                ans++;
            }
        }
        return ans;
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.