C++의 이진 표현에서 설정된 비트의 소수

이 문제에서는 두 개의 정수 L과 R이 주어집니다. 우리의 과제는 L에서 R 사이에 있는 소수로 계산되는 비트를 가진 총 숫자를 인쇄하는 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

Input: L = 7, R = 12
Output: 6
Explanation:
7 -> 111 , set bits = 2, prime number.
8 -> 1000 , set bits = 1, not prime number.
9 -> 1001 , set bits = 2, prime number
10 -> 1010 , set bits = 2, prime number
11 -> 1011, set bits = 3, prime number
12 -> 1100, set bits = 2, prime number

이 문제를 해결하기 위해 범위 내의 모든 요소를 ​​순회합니다. 그리고 숫자에서 설정된 비트의 총 수를 확인합니다. 이를 위해 우리는 CPP _builtin_popcount()에서 미리 정의된 함수를 사용할 것입니다. 그런 다음 소수에 대한 숫자의 세트 비트를 확인합니다. 그렇다면 숫자를 늘리십시오. 그렇지 않으면 그렇지 않습니다.

솔루션 구현을 보여주는 프로그램

예시

#include <iostream>
using namespace std;
bool isPrimeNumber(int n) {
   if (n <= 1) return false;
   if (n <= 3) return true;
   if (n%2 == 0 || n%3 == 0) return false;
   for (int i=5; i*i<=n; i=i+6)
   if (n%i == 0 || n%(i+2) == 0)
   return false;
   return true;
}
void printPrimeSetBits(int l, int r) {
   int tot_bit, count = 0;
   for (int i = l; i <= r; i++) {
      tot_bit = __builtin_popcount(i);
      if (isPrimeNumber(tot_bit))
         count++;
   }
   cout<<count;
}
int main() {
   int L = 7, R = 13;
   cout<<"Total numbers with prime set bits between "<<L<<" and "<<R<<" are : ";
   printPrimeSetBits(L, R);
   return 0;
}

출력

Total numbers with prime set bits between 7 and 13 are : 6