【LeetCode】762. Prime Number of Set Bits in Binary Representation

Pythonバージョン:python 3.6.2
762. Prime Number of Set Bits in Binary Representation
Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bitsin 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, 21written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)
Example 1:Input: L = 6, R = 10Output: 4Explanation: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:Input: L = 10, R = 15Output: 5Explanation: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)

class Solution:
    def countPrimeSetBits(self, L, R):
        """
        :type L: int
        :type R: int
        :rtype: int
        """
        res = 0
        for i in range(L, R+1):
            count_1 = bin(i)[2:].count('1')
            if count_1 > 1:
                flag = 0
                for j in range(2, count_1):
                    if not count_1 % j:
                        flag += 1
                if not flag:
                    res += 1
        return res

この問題の主な鍵は素数かどうかを判断することであり、ネット上には他の解法があり、比較的良いのは:
この数が自分の小さい数ごとに割り切れないかを判断するのではなく、この数の平均根値を判断します.
上記コードの13行目をfor j in range(2,math.sqrt(count_1)+1)に変更する
同時にimport mathを覚えています