<p>Given two integers <code>left</code> and <code>right</code>, return <em>the <strong>count</strong> of numbers in the <strong>inclusive</strong> range </em><code>[left, right]</code><em> having a <strong>prime number of set bits</strong> in their binary representation</em>.</p>

<p>Recall that the <strong>number of set bits</strong> an integer has is the number of <code>1</code>&#39;s present when written in binary.</p>

<ul>
	<li>For example, <code>21</code> written in binary is <code>10101</code>, which has <code>3</code> set bits.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> left = 6, right = 10
<strong>Output:</strong> 4
<strong>Explanation:</strong>
6  -&gt; 110 (2 set bits, 2 is prime)
7  -&gt; 111 (3 set bits, 3 is prime)
8  -&gt; 1000 (1 set bit, 1 is not prime)
9  -&gt; 1001 (2 set bits, 2 is prime)
10 -&gt; 1010 (2 set bits, 2 is prime)
4 numbers have a prime number of set bits.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> left = 10, right = 15
<strong>Output:</strong> 5
<strong>Explanation:</strong>
10 -&gt; 1010 (2 set bits, 2 is prime)
11 -&gt; 1011 (3 set bits, 3 is prime)
12 -&gt; 1100 (2 set bits, 2 is prime)
13 -&gt; 1101 (3 set bits, 3 is prime)
14 -&gt; 1110 (3 set bits, 3 is prime)
15 -&gt; 1111 (4 set bits, 4 is not prime)
5 numbers have a prime number of set bits.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= left &lt;= right &lt;= 10<sup>6</sup></code></li>
	<li><code>0 &lt;= right - left &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution {
public:
    int countPrimeSetBits(int left, int right) {
        vector<int> v;
        int countt=0;
        for (int i = left; i < right + 1; i++) {
            int n = i;

            int count = 0;
            string nb;
            while (n > 0) {
                nb += (n % 2 == 0) ? '0' : '1';
                if (n % 2 != 0) {

                    count++;
                }
                n /= 2;
            }
            v.push_back(count);
        }
        int nnn = v.size();
        for (int i = 0; i < nnn; i++) {
            cout << v[i] << " ";
        }
        cout << endl;
        cout << endl;
        for (int i = 0; i < nnn; i++) {
            int num = v[i];
            bool flag = false;
            if (num == 1) {
                flag = true;
            } else {
                for (int i = 2; i < num; i++) {
                    if (num % i == 0) {

                        flag = true;
                        break;
                    } else {
                        flag = false;

                    }
                }
            }
            cout << endl;
            if (flag == true) {
                cout << " not prime";
            } else {
                cout << "prime..";
                countt++;
            }
        }
        return countt;
    }
};
49000