{"id":8867,"date":"2024-05-24T13:01:03","date_gmt":"2024-05-24T05:01:03","guid":{"rendered":""},"modified":"2024-05-24T13:01:03","modified_gmt":"2024-05-24T05:01:03","slug":"appcode\u662f\u4ec0\u4e48\u610f\u601d_the code of\u300c\u5efa\u8bae\u6536\u85cf\u300d","status":"publish","type":"post","link":"https:\/\/mushiming.com\/8867.html","title":{"rendered":"appcode\u662f\u4ec0\u4e48\u610f\u601d_the code of\u300c\u5efa\u8bae\u6536\u85cf\u300d"},"content":{"rendered":"<p><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"display: none;\"> \n <path stroke-linecap=\"round\" d=\"M5,0 0,2.5 5,5z\" id=\"raphael-marker-block\" style=\"-webkit-tap-highlight-color: rgba(0, 0, 0, 0);\"><\/path> \n<\/svg> <\/p>\n<ol start=\"1046\">\n<li>Prime Number of Set Bits in Binary Representation<br \/> Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.<\/li>\n<\/ol>\n<p>(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)<\/p>\n<p>Example<br \/> Example 1:<\/p>\n<p>Input: L = 6, R = 10<br \/> Output: 4<br \/> Explanation:<br \/> 6 -&gt; 110 (2 set bits, 2 is prime)<br \/> 7 -&gt; 111 (3 set bits, 3 is prime)<br \/> 9 -&gt; 1001 (2 set bits , 2 is prime)<br \/> 10-&gt;1010 (2 set bits , 2 is prime)<br \/> Example 2:<\/p>\n<p>Input: L = 10, R = 15<br \/> Output: 5<br \/> Explanation:<br \/> 10 -&gt; 1010 (2 set bits, 2 is prime)<br \/> 11 -&gt; 1011 (3 set bits, 3 is prime)<br \/> 12 -&gt; 1100 (2 set bits, 2 is prime)<br \/> 13 -&gt; 1101 (3 set bits, 3 is prime)<br \/> 14 -&gt; 1110 (3 set bits, 3 is prime)<br \/> 15 -&gt; 1111 (4 set bits, 4 is not prime)<br \/> Notice<br \/> 1.L, R will be integers L &lt;= R in the range [1, 10^6].<br \/> 2.R - L will be at most 10000.<\/p>\n<p>\u6c42Prime\u6570\u7684\u7ec3\u4e60\u9898\u3002<\/p>\n<pre class=\"language-java prettyprint linenums\"><code>class Solution {\npublic:\n    \/**\n     * @param L: an integer\n     * @param R: an integer\n     * @return: the count of numbers in the range [L, R] having a prime number of set bits in their binary representation\n     *\/\n    int countPrimeSetBits(int L, int R) {\n        int result = 0;\n        for (int i = L; i &lt;= R; ++i) {\n            if (isPrime(numOfSetBits(i))) {\n                result++;\n            }\n        }\n        return result;\n    }\n\nprivate:\n    inline int numOfSetBits(int n) {\n        int count = 0;\n        while (n &gt; 0) {\n            if (n &amp; 1) {\n                count++;\n            }\n            n &gt;&gt;= 1;\n        }\n        return count;\n    }\n\n    inline int isPrime(int n) {\n        if (n &lt;= 1) return false;\n        if (n == 2) return true;\n        if ((n &amp; 0x1) == 0) return false;\n        int sqrtN = sqrt(n);\n        for (int i = 2; i &lt;= sqrtN; ++i) {\n            if ((n % i) == 0) return false;\n        }\n        return true;\n    }    \n};\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"appcode\u662f\u4ec0\u4e48\u610f\u601d_the code of\u300c\u5efa\u8bae\u6536\u85cf\u300dLintCode-LogoHomeAlgorithmsAICATnewVIPLanguageavatarroufooBack1046.PrimeNumb...","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"_links":{"self":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/posts\/8867"}],"collection":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/comments?post=8867"}],"version-history":[{"count":0,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/posts\/8867\/revisions"}],"wp:attachment":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/media?parent=8867"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/categories?post=8867"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/tags?post=8867"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}