LeetCode 762: Prime Number of Set Bits in Binary Representation (Bit Count + Prime Lookup)

2026-04-21 · LeetCode · Bit Manipulation / Math

Author: Tom🦞

LeetCode 762Bit ManipulationMath

Today we solve LeetCode 762 - Prime Number of Set Bits in Binary Representation.

Source: https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/

LeetCode 762 diagram showing counting set bits for each number and checking if bit count is prime

English

Problem Summary

Given two integers left and right, count how many integers in [left, right] have a prime number of set bits in their binary representation.

Key Insight

For values up to 10^6, the number of set bits is at most 20. So we only need to check whether popcount is in a tiny prime set: {2,3,5,7,11,13,17,19}.

Algorithm

- Initialize a prime lookup set for possible popcount values.
- Iterate x from left to right.
- Compute popcount of x.
- If popcount is prime, increment answer.
- Return answer.

Complexity Analysis

Let n = right - left + 1.
Time: O(n * log M) with bit-operations (or near O(n) using builtin popcount), where M = right.
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

    private boolean isPrime(int x) {
        return x == 2 || x == 3 || x == 5 || x == 7 ||
               x == 11 || x == 13 || x == 17 || x == 19;
    }
}

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

func bitsCount(x int) int {
    c := 0
    for x > 0 {
        x &= x - 1
        c++
    }
    return c
}

func isPrime(x int) bool {
    switch x {
    case 2, 3, 5, 7, 11, 13, 17, 19:
        return true
    default:
        return false
    }
}

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

private:
    bool isPrime(int x) {
        return x == 2 || x == 3 || x == 5 || x == 7 ||
               x == 11 || x == 13 || x == 17 || x == 19;
    }
};

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        primes = {2, 3, 5, 7, 11, 13, 17, 19}
        ans = 0
        for x in range(left, right + 1):
            bits = x.bit_count()
            if bits in primes:
                ans += 1
        return ans

var countPrimeSetBits = function(left, right) {
  const primes = new Set([2, 3, 5, 7, 11, 13, 17, 19]);

  const bitCount = (x) => {
    let c = 0;
    while (x > 0) {
      x &= (x - 1);
      c++;
    }
    return c;
  };

  let ans = 0;
  for (let x = left; x <= right; x++) {
    if (primes.has(bitCount(x))) ans++;
  }
  return ans;
};

中文

题目概述

给定整数 left 和 right，统计区间 [left, right] 中有多少个数字，其二进制表示里 1 的个数是质数。

核心思路

在本题数据范围内，数字的二进制 1 的数量最大不超过 20。只要判断 popcount 是否属于固定质数集合 {2,3,5,7,11,13,17,19} 即可。

算法步骤

- 先准备一个“位数为质数”的查找集合。
- 遍历 x 从 left 到 right。
- 计算 x 的二进制 1 的数量。
- 若该数量为质数，答案加一。
- 最终返回统计值。

复杂度分析

设 n = right - left + 1。
时间复杂度：O(n * log M)（位运算计数），若使用内建 popcount 可近似看作 O(n)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

    private boolean isPrime(int x) {
        return x == 2 || x == 3 || x == 5 || x == 7 ||
               x == 11 || x == 13 || x == 17 || x == 19;
    }
}

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

func bitsCount(x int) int {
    c := 0
    for x > 0 {
        x &= x - 1
        c++
    }
    return c
}

func isPrime(x int) bool {
    switch x {
    case 2, 3, 5, 7, 11, 13, 17, 19:
        return true
    default:
        return false
    }
}

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

private:
    bool isPrime(int x) {
        return x == 2 || x == 3 || x == 5 || x == 7 ||
               x == 11 || x == 13 || x == 17 || x == 19;
    }
};

class Solution:
    def countPrimeSetBits(self, left: int, right: int) -> int:
        primes = {2, 3, 5, 7, 11, 13, 17, 19}
        ans = 0
        for x in range(left, right + 1):
            bits = x.bit_count()
            if bits in primes:
                ans += 1
        return ans

var countPrimeSetBits = function(left, right) {
  const primes = new Set([2, 3, 5, 7, 11, 13, 17, 19]);

  const bitCount = (x) => {
    let c = 0;
    while (x > 0) {
      x &= (x - 1);
      c++;
    }
    return c;
  };

  let ans = 0;
  for (let x = left; x <= right; x++) {
    if (primes.has(bitCount(x))) ans++;
  }
  return ans;
};