【每日一题20220802】二进制表示中质数个计算置位

题目难度:简单
题目来源:762. 二进制表示中质数个计算置位 - 力扣(LeetCode)

描述

:mage:给你两个整数 left 和 right ,在闭区间 [left, right] 范围内,统计并返回计算置位位数为质数的整数个数。
计算置位位数就是二进制表示中 1 的个数。

  • 例如, 21的二进制表示10101有3个计算置位。

编写一个函数, 完成上述操作

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
    # your code here

示例 1:

输入:left = 6, right = 10
输出:4
解释:
6 -> 110 (2 个计算置位,2 是质数)
7 -> 111 (3 个计算置位,3 是质数)
9 -> 1001 (2 个计算置位,2 是质数)
10-> 1010 (2 个计算置位,2 是质数)
共计 4 个计算置位为质数的数字。

示例 2:

输入:left = 10, right = 15
输出:5
解释:
10 -> 1010 (2 个计算置位, 2 是质数)
11 -> 1011 (3 个计算置位, 3 是质数)
12 -> 1100 (2 个计算置位, 2 是质数)
13 -> 1101 (3 个计算置位, 3 是质数)
14 -> 1110 (3 个计算置位, 3 是质数)
15 -> 1111 (4 个计算置位, 4 不是质数)
共计 5 个计算置位为质数的数字。

提示:

  • 1 <= left <= right <= 10^6
  • 0 <= right - left <= 10^4

可以顺便写出自己的答案

我来打个样。

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        # your code here
        result = 0
        for i in range(left, right+1):
            site_num = bin(i)[2:].count("1")
            if site_num > 1:
                for n in range(2, site_num):
                    if (site_num % n) == 0:
                        break
                else:
                    result += 1
        return result
1 Like
def countPrimeSetBits(self, left: int, right: int) -> int:
        res_cn = 0
        for i in range(left,right+1):
            count = bin(i).count('1')
            if count in {2,3,5,7,11,13,17,19,23,29,31}:
                res_cn += 1
        return res_cn
关闭