Giả sử ta có hai số nguyên L và R, ta cần đếm số lượng số trong khoảng [L, R] (tính cả hai đầu) có số bit 1 (set bits) trong biểu diễn nhị phân là số nguyên tố.
Ví dụ, nếu đầu vào là L = 6 và R = 10, thì đầu ra sẽ là 4, vì có 4 số: 6(110), 7(111), 9(1001), 10(1010), tất cả đều có số bit 1 là số nguyên tố.
Để giải quyết, ta thực hiện các bước sau:
- count := 0
- Với j từ L đến R, thực hiện:
- Nếu số bit 1 của j nằm trong [2,3,5,7,11,13,17,19], thì:
- count := count + 1
- Trả về count
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
class Solution: def countPrimeSetBits(self, L, R): def popcount(i): return bin(i)[2:].count('1') count = 0 for j in range(L, R+1): if popcount(j) in [2,3,5,7,11,13,17,19]: count += 1 return count ob = Solution() print(ob.countPrimeSetBits(6,10))Đầu vào
6,10
Đầu ra
4