一起养成写作习惯！这是我参与「掘金日新计划 · 4 月更文挑战」的第5天，点击查看活动详情。

【刷题日记】762. 二进制表示中质数个计算置位

本次刷题日记的第 25 篇，力扣题为：762. 二进制表示中质数个计算置位 ，简单

一、题目描述：

清明小长假第 3 天，回到深圳后稍加调整，看看今天 leetcode 是个啥题？还是要保持习惯，每天总要花点时间做点自己想做的事情

仔细看一下是个简单题，今晚应该可以早点睡觉了

二、这道题考察了什么思想？你的思路是什么？

我们还是要认真细致的来查看一下该题本身给我们传达的信息：

• 题中会给出一个区间，区间内的数据都是整数，我们需要计算出这个区间内的每一个数字的二进制数中 1 的个数
• 我们需要知道如何去校验一个数是否是质数
• 完成上述 2 步之后，我们就可以使用傻瓜式的遍历方式来实现本题了

计算一个数的二进制数包含多少个 1 ，我们可以使用辗转相除法来进行处理，当然，我们也可以使用库函数来进行处理，此处我们使用的是 golang ，那么我们直接使用库函数计算的话，可以这样来使用 ： bits.OnesCount(具体的 uint 数字)

那么问题就来到了什么是质数了？

如果一个数 大于 1 的数字，并且这个数字只能被 1 和 自身整除，不能被其他任何数字整除，那么这个数字就是 质数

关于如何校验一个数是质数，我们在大学学习 C 语言的时候，就学习并且实践过，在这里咱不再赘述了

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码

编码如下：

func countPrimeSetBits(left int, right int) (res int) {
  // 直接傻瓜式的遍历
    for i:=left;i<=right;i++ {
        // golang 中 使用 bits.OnesCount() 来计算 uint 数中 1 个个数
        if isPrimeNum(bits.OnesCount(uint(i))){
            res++
        }
    }
    return
}
// 校验是否是质数
func isPrimeNum(num int) bool {
    if num < 2 {
        return false
    }
    for i:=2; i*i <= num; i++ {
        if num %i == 0 {
            return false
        }
    }
    return true
}

看了这个题的编码其实也非常的常规

• 第一步 遍历题目给出的数组
• 第二步 计算具体数字的二进制数中的 1 的个数
• 校验传入的数据是否是质数

四、总结：

那么，对于这个题，他的空间复杂度很明显，是 O(1) ，因为我们只引入了常数级别的空间消耗

那么他的时间复杂度是多少呢？ xdm 你们有一个清晰的概念吗 ，感兴趣的可以尝试计算一下他的时间复杂度，暂时先不明确的写出来了

原题地址：762. 二进制表示中质数个计算置位

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~