Prime Number of Set Bits ใน Python: นับจำนวนที่มีบิต 1 เป็นจำนวนเฉพาะ

ได้รับจำนวนเต็ม L และ R นับจำนวนในช่วง [L, R] ที่มีจำนวนบิต 1 (set bits) ในรูปแบบไบนารีเป็นจำนวนเฉพาะ

ตัวอย่าง

L=6, R=10 → 6(110), 7(111), 9(1001), 10(1010) มี set bits = 2,3,2,2 (ล้วนเป็นเฉพาะ) → ผลลัพธ์ 4

ขั้นตอนการแก้ปัญหา

1. จำนวนเฉพาะที่เป็นไปได้สำหรับ set bits (สูงสุด 20 บิตสำหรับ int 32-bit): [2,3,5,7,11,13,17,19]
2. วน j จาก L ถึง R
3. นับ set bits ด้วย bin(j).count('1')
4. ถ้าอยู่ในรายการเฉพาะ → เพิ่มตัวนับ
5. คืนตัวนับ

การติดตั้งใน Python

class Solution:
    def countPrimeSetBits(self, L, R):
        primes = {2,3,5,7,11,13,17,19}
        count = 0
        for j in range(L, R+1):
            if bin(j).count('1') in primes:
                count += 1
        return count

ob = Solution()
print(ob.countPrimeSetBits(6, 10))  # 4

อินพุต / เอาต์พุต

Input: 6, 10
Output: 4