题目大意：求给定范围内，数的二进制形式中1的个数为素数个的数字的个数。
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.
(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.)
Example 1:
|
1 2 3 4 5 6 7 |
Input: L = 6, R = 10 Output: 4 Explanation: 6 -> 110 (2 set bits, 2 is prime) 7 -> 111 (3 set bits, 3 is prime) 9 -> 1001 (2 set bits , 2 is prime) 10->1010 (2 set bits , 2 is prime) |
Example 2:
|
1 2 3 4 5 6 7 8 9 |
Input: L = 10, R = 15 Output: 5 Explanation: 10 -> 1010 (2 set bits, 2 is prime) 11 -> 1011 (3 set bits, 3 is prime) 12 -> 1100 (2 set bits, 2 is prime) 13 -> 1101 (3 set bits, 3 is prime) 14 -> 1110 (3 set bits, 3 is prime) 15 -> 1111 (4 set bits, 4 is not prime) |
Note:
L, Rwill be integersL <= Rin the range[1, 10^6].R - Lwill be at most 10000.
Solution 1: Brute Force
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// Author: Huahua // Running time: 22 ms class Solution { public: int countPrimeSetBits(int L, int R) { int ans = 0; for (int n = L; n <= R; ++n) if (isPrime(bits(n))) ++ans; return ans; } private: bool isPrime(int n) { if (n <= 1) return false; if (n == 2) return true; for (int i = 2; i <= sqrt(n); ++i) if (n % i == 0) return false; return true; } int bits(int n) { int s = 0; while (n) { s += n & 1; n >>= 1; } return s; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua // Running time: 16 ms class Solution { public: int countPrimeSetBits(int L, int R) { int ans = 0; set<int> primes{2, 3, 5, 7, 11, 13, 17, 19}; for (int n = L; n <= R; ++n) if (primes.count(__builtin_popcountll(n))) ++ans; return ans; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua // Running time: 30 ms class Solution { public: int countPrimeSetBits(int L, int R) { int ans = 0; unordered_set<int> primes{2, 3, 5, 7, 11, 13, 17, 19}; for (int n = L; n <= R; ++n) if (primes.count(__builtin_popcountll(n))) ++ans; return ans; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua // Running time: 9 ms class Solution { public: int countPrimeSetBits(int L, int R) { int ans = 0; vector<int> p(20, 0); p[2] = p[3] = p[5] = p[7] = p[11] = p[13] = p[17] = p[19] = 1; for (int n = L; n <= R; ++n) if (p[__builtin_popcountll(n)]) ++ans; return ans; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua // Running time: 8 ms class Solution { public: int countPrimeSetBits(int L, int R) { constexpr int magic = 665772; int ans = 0; for (int n = L; n <= R; ++n) if (magic & (1 << __builtin_popcountll(n))) ++ans; return ans; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Author: Huahua // Running time: 39 ms class Solution { public int countPrimeSetBits(int L, int R) { int ans = 0; for (int n = L; n <= R; ++n) if (isPrime(bits(n))) ++ans; return ans; } private boolean isPrime(int n) { if (n <= 1) return false; if (n == 2) return true; for (int i = 2; i <= (int)Math.sqrt(n); ++i) if (n % i == 0) return false; return true; } private int bits(int n) { int s = 0; while (n != 0) { s += n & 1; n >>= 1; } return s; } } |
Python2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
""" Author: Huahua Running time: 1618 ms """ class Solution(object): def countPrimeSetBits(self, L, R): def isPrime(n): if n <= 1: return False if n == 2: return True for i in range(2, int(math.sqrt(n)) + 1): if n % i == 0: return False return True def bits(n): s = 0 while n != 0: s += n & 1 n >>= 1 return s ans = 0 for n in range(L, R + 1): if isPrime(bits(n)): ans += 1 return ans |
Python2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
""" Author: Huahua Running time: 1163 ms """ class Solution(object): def countPrimeSetBits(self, L, R): def bits(n): s = 0 while n != 0: s += n & 1 n >>= 1 return s primes = set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]) ans = 0 for n in range(L, R + 1): if bits(n) in primes: ans += 1 return ans |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
""" Author: Huahua Running time: 667 ms """ class Solution(object): def countPrimeSetBits(self, L, R): def bits(n): s = 0 while n != 0: n &= n - 1; s += 1 return s ans = 0 while L <= R: if (665772 >> bits(L)) & 1 > 0: ans += 1 L += 1 return ans |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment