二进制表示中质数个计算置位

762. 二进制表示中质数个计算置位

给你两个整数 left 和 right ，在闭区间 [left, right] 范围内，统计并返回 计算置位位数为质数 的整数个数。

计算置位位数 就是二进制表示中 1 的个数。

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

示例 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⁶
0 <= right - left <= 10⁴

相似题目

位1的个数

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int countPrimeSetBits(int left, int right) { } };

rust 解法, 执行用时: 0 ms, 内存消耗: 2.3 MB, 提交时间: 2023-09-15 10:30:07

impl Solution {
    pub fn count_prime_set_bits(left: i32, right: i32) -> i32 {
        (left..=right).fold(0, |acc, n| {
            acc + if 665772 & 1 << n.count_ones() > 0 {
                1
            } else {
                0
            }
        })
    }
}

rust 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2023-09-15 10:29:41

impl Solution {
    pub fn count_prime_set_bits(left: i32, right: i32) -> i32 {
        (left..=right).filter(|i| [2, 3, 5, 7, 11, 13, 17, 19].contains(&i.count_ones())).count() as i32
    }
}

javascript 解法, 执行用时: 540 ms, 内存消耗: 46.8 MB, 提交时间: 2023-09-15 10:27:31

/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
var countPrimeSetBits = function(left, right) {
    let ans = 0;
    for (let x = left; x <= right; ++x) {
        if (((1 << bitCount(x)) & 665772) != 0) {
            ++ans;
        }
    }
    return ans;
};

const bitCount = (x) => {
    return x.toString(2).split('0').join('').length;
}

cpp 解法, 执行用时: 4 ms, 内存消耗: 6.1 MB, 提交时间: 2023-09-15 10:27:12

class Solution {
public:
    int countPrimeSetBits(int left, int right) {
        int ans = 0;
        for (int x = left; x <= right; ++x) {
            if ((1 << __builtin_popcount(x)) & 665772) {
                ++ans;
            }
        }
        return ans;
    }
};

python3 解法, 执行用时: 100 ms, 内存消耗: 15.8 MB, 提交时间: 2023-09-15 10:26:35

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        return sum(((1 << x.bit_count()) & 665772) != 0 for x in range(left, right + 1))

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-09-15 10:26:19

func countPrimeSetBits(left, right int) (ans int) {
    for x := left; x <= right; x++ {
        if 1<<bits.OnesCount(uint(x))&665772 != 0 {
            ans++
        }
    }
    return
}

java 解法, 执行用时: 2 ms, 内存消耗: 38.2 MB, 提交时间: 2023-09-15 10:25:59

/**
 * 质数判断优化，10^6 < 2^20, 因此1个数不超过19
 * 不超过19 的质数有 2,3,5,7,11,13,17,19
 * 我们可以用一个二进制数 mask=665772=10100010100010101100（二进制）来存储这些质数
 * mask 二进制的从低到高的第 i 位为 1 表示 i 是质数，为 0 表示 i 不是质数
 * 设整数 x 的二进制中 1 的个数为 c，若 mask 按位与 2^c 不为 0，则说明 c 是一个质数
 */
class Solution {
    public int countPrimeSetBits(int left, int right) {
        int ans = 0;
        for (int x = left; x <= right; ++x) {
            if (((1 << Integer.bitCount(x)) & 665772) != 0) {
                ++ans;
            }
        }
        return ans;
    }
}

java 解法, 执行用时: 4 ms, 内存消耗: 38 MB, 提交时间: 2023-09-15 10:20:16

class Solution {
    public int countPrimeSetBits(int left, int right) {
        int ans = 0;
        for (int x = left; x <= right; ++x) {
            if (isPrime(Integer.bitCount(x))) {
                ++ans;
            }
        }
        return ans;
    }

    private boolean isPrime(int x) {
        if (x < 2) {
            return false;
        }
        for (int i = 2; i * i <= x; ++i) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}

javascript 解法, 执行用时: 564 ms, 内存消耗: 46.7 MB, 提交时间: 2023-09-15 10:19:53

/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
var countPrimeSetBits = function(left, right) {
    let ans = 0;
    for (let x = left; x <= right; ++x) {
        if (isPrime(bitCount(x))) {
            ++ans;
        }
    }
    return ans;
};

const isPrime = (x) => {
    if (x < 2) {
        return false;
    }
    for (let i = 2; i * i <= x; ++i) {
        if (x % i === 0) {
            return false;
        }
    }
    return true;
}

const bitCount = (x) => {
    return x.toString(2).split('0').join('').length;
}

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-09-15 10:19:22

func isPrime(x int) bool {
    if x < 2 {
        return false
    }
    for i := 2; i*i <= x; i++ {
        if x%i == 0 {
            return false
        }
    }
    return true
}

func countPrimeSetBits(left, right int) (ans int) {
    for x := left; x <= right; x++ {
        if isPrime(bits.OnesCount(uint(x))) {
            ans++
        }
    }
    return
}

python3 解法, 执行用时: 148 ms, 内存消耗: 15.8 MB, 提交时间: 2023-09-15 10:18:55

class Solution:
    def isPrime(self, x: int) -> bool:
        if x < 2:
            return False
        i = 2
        while i * i <= x:
            if x % i == 0:
                return False
            i += 1
        return True

    def countPrimeSetBits(self, left: int, right: int) -> int:
        return sum(self.isPrime(x.bit_count()) for x in range(left, right + 1))

php 解法, 执行用时: 152 ms, 内存消耗: 15.1 MB, 提交时间: 2021-05-14 18:36:45

class Solution {

    /**
     * @param Integer $left
     * @param Integer $right
     * @return Integer
     */
    function countPrimeSetBits($left, $right) {
        $ans = 0;
        $primes = [2,3,5,7,11,13,17,19];
        for ( $i=$left;$i<=$right;$i++ ) {
            if ( in_array($this->hammingWeight($i), $primes, true) )
                $ans++;
        }
        return $ans;
    }

    function hammingWeight(int $n)
    {
        $ans = 0;
        while ( $n != 0 ) {
            $n &= $n - 1;  // 与运算, 每次会消掉
            $ans++;
        }
        return $ans;
    }
}

上一题

下一题

详情