762. Prime Number of Set Bits in Binary Representation

Loading...LeetCode

难道就是考我判断质数...？

class Solution:
    def countPrimeSetBits(self, L: int, R: int) -> int:
        def isPrime(n) : 
            if (n <= 1) : return False
            if (n <= 3) : return True
            if (n % 2 == 0 or n % 3 == 0) : return False
            i = 5
            while(i * i <= n) : 
                if (n % i == 0 or n % (i + 2) == 0) : return False
                i = i + 6
            return True
        
        res = 0
        for N in range(L, R+1):
            if isPrime(bin(N).count("1")): res += 1
        return res

update 看到的另一个思路，不用判断质数：

L, R will be integers L <= R in the range [1, 10^6], 10^6 < 2^20

所以直接保存20以内的质数进行查找判断即可。空间换时间的一个思路。

class Solution(object):
    def countPrimeSetBits(self, L, R):
        """
        :type L: int
        :type R: int
        :rtype: int
        """
        primes = [2, 3, 5, 7, 11, 13, 17, 19]
        res = 0
        for num in range(L, R + 1):
            if bin(num).count("1") in primes:
                res += 1
        return res