C++でのバイナリ表現のセットビットの素数

この問題では、2つの整数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