题目大意:求给定范围内,数的二进制形式中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 1
s 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, R
will be integersL <= R
in the range[1, 10^6]
.R - L
will 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.
Be First to Comment