方法一：暴力枚举
枚举 $[\textit{left},\textit{right}]$ 中的整数 $x$，计算 $x$ 二进制中的 $1$ 的个数 $c$。如果 $c$ 是质数，那么答案增加一。
由于 $[1,10^6]$ 中的二进制数至多有 $19$ 个 $1$，所以只需 $19$ 以内的质数，即
$$
2, 3, 5, 7, 11, 13, 17, 19
$$
primes = {2, 3, 5, 7, 11, 13, 17, 19}
class Solution:
def countPrimeSetBits(self, left: int, right: int) -> int:
ans = 0
for x in range(left, right + 1):
if x.bit_count() in primes:
ans += 1
return ans
class Solution {
private static final Set<Integer> primes = Set.of(2, 3, 5, 7, 11, 13, 17, 19);
public int countPrimeSetBits(int left, int right) {
int ans = 0;
for (int x = left; x <= right; x++) {
if (primes.contains(Integer.bitCount(x))) {
ans++;
}
}
return ans;
}
}
class Solution {
// 注：也可以用哈希集合做，由于本题质数很少，用数组也可以
static constexpr int primes[] = {2, 3, 5, 7, 11, 13, 17, 19};
public:
int countPrimeSetBits(int left, int right) {
int ans = 0;
for (uint32_t x = left; x <= right; x++) {
if (ranges::contains(primes, popcount(x))) {
ans++;
}
}
return ans;
}
};
// 注：也可以用哈希集合做，由于本题质数很少，用 slice 也可以
var primes = []int{2, 3, 5, 7, 11, 13, 17, 19}
func countPrimeSetBits(left, right int) (ans int) {
for x := left; x <= right; x++ {
if slices.Contains(primes, bits.OnesCount(uint(x))) {
ans++
}
}
return
}
复杂度分析
- 时间复杂度：$\mathcal{O}(\textit{right}-\textit{left})$。
- 空间复杂度：$\mathcal{O}(1)$。不计入质数集合的空间。
方法二：上下界数位 DP
数位 DP v1.0 模板讲解
数位 DP v2.0 模板讲解（上下界数位 DP）
对于本题，在递归边界（$i=n$）我们需要判断是否填了质数个 $1$，所以需要参数 $\textit{cnt}_1$ 表示填过的 $1$ 的个数。其余同 v2.0 模板。
primes = {2, 3, 5, 7, 11, 13, 17, 19}
class Solution:
def countPrimeSetBits(self, left: int, right: int) -> int:
high_s = list(map(int, bin(right)[2:])) # 避免在 dfs 中频繁调用 int()
n = len(high_s)
low_s = list(map(int, bin(left)[2:].zfill(n))) # 添加前导零，长度和 high_s 对齐
# 在 dfs 的过程中，统计二进制中的 1 的个数 cnt1
@cache # 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）
def dfs(i: int, cnt1: int, limit_low: bool, limit_high: bool) -> int:
if i == n:
return 1 if cnt1 in primes else 0
lo = low_s[i] if limit_low else 0
hi = high_s[i] if limit_high else 1
res = 0
for d in range(lo, hi + 1):
res += dfs(i + 1, cnt1 + d, limit_low and d == lo, limit_high and d == hi)
return res
return dfs(0, 0, True, True)
class Solution {
private static final Set<Integer> primes = Set.of(2, 3, 5, 7, 11, 13, 17, 19);
public int countPrimeSetBits(int left, int right) {
int n = 32 - Integer.numberOfLeadingZeros(right);
int[][] memo = new int[n][n + 1];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return dfs(n - 1, 0, true, true, left, right, memo);
}
// 在 dfs 的过程中，统计二进制中的 1 的个数 cnt1
private int dfs(int i, int cnt1, boolean limitLow, boolean limitHigh, int left, int right, int[][] memo) {
if (i < 0) {
return primes.contains(cnt1) ? 1 : 0;
}
if (!limitLow && !limitHigh && memo[i][cnt1] != -1) {
return memo[i][cnt1];
}
int lo = limitLow ? left >> i & 1 : 0;
int hi = limitHigh ? right >> i & 1 : 1;
int res = 0;
for (int d = lo; d <= hi; d++) {
res += dfs(i - 1, cnt1 + d, limitLow && d == lo, limitHigh && d == hi, left, right, memo);
}
if (!limitLow && !limitHigh) {
memo[i][cnt1] = res;
}
return res;
}
}
class Solution {
// 注：也可以用哈希集合做，由于本题质数很少，用数组也可以
static constexpr int primes[] = {2, 3, 5, 7, 11, 13, 17, 19};
public:
int countPrimeSetBits(int left, int right) {
int n = bit_width((uint32_t) right);
vector memo(n, vector<int>(n + 1, -1));
// 在 dfs 的过程中，统计二进制中的 1 的个数 cnt1
auto dfs = [&](this auto&& dfs, int i, int cnt1, bool limit_low, bool limit_high) -> int {
if (i < 0) {
return ranges::contains(primes, cnt1);
}
if (!limit_low && !limit_high && memo[i][cnt1] != -1) {
return memo[i][cnt1];
}
int lo = limit_low ? left >> i & 1 : 0;
int hi = limit_high ? right >> i & 1 : 1;
int res = 0;
for (int d = lo; d <= hi; d++) {
res += dfs(i - 1, cnt1 + d, limit_low && d == lo, limit_high && d == hi);
}
if (!limit_low && !limit_high) {
memo[i][cnt1] = res;
}
return res;
};
return dfs(n - 1, 0, true, true);
}
};
// 注：也可以用哈希集合做，由于本题质数很少，用数组也可以
var primes = []int{2, 3, 5, 7, 11, 13, 17, 19}
func countPrimeSetBits(left int, right int) int {
n := bits.Len(uint(right))
memo := make([][]int, n)
for i := range memo {
memo[i] = make([]int, n+1)
for j := range memo[i] {
memo[i][j] = -1
}
}
// 在 dfs 的过程中，统计二进制中的 1 的个数 cnt1
var dfs func(int, int, bool, bool) int
dfs = func(i, cnt1 int, limitLow, limitHigh bool) (res int) {
if i < 0 {
if slices.Contains(primes, cnt1) {
return 1
}
return 0
}
if !limitLow && !limitHigh {
p := &memo[i][cnt1]
if *p >= 0 {
return *p
}
defer func() { *p = res }()
}
lo := 0
if limitLow {
lo = left >> i & 1
}
hi := 1
if limitHigh {
hi = right >> i & 1
}
for d := lo; d <= hi; d++ {
res += dfs(i-1, cnt1+d, limitLow && d == lo, limitHigh && d == hi)
}
return
}
return dfs(n-1, 0, true, true)
}
复杂度分析
- 时间复杂度：$\mathcal{O}(\log^2 \textit{right})$。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(\log^2 \textit{right})$，单个状态的计算时间为 $\mathcal{O}(1)$，所以总的时间复杂度为 $\mathcal{O}(\log^2 \textit{right})$。
- 空间复杂度：$\mathcal{O}(\log^2 \textit{right})$。保存多少状态，就需要多少空间。
方法三：组合数学
primes = [2, 3, 5, 7, 11, 13, 17, 19]
class Solution:
def calc(self, high: int) -> int:
# 转换成计算 < high + 1 的合法正整数个数
# 这样转换可以方便下面的代码把 high 也算进来
high += 1
res = ones = 0
for i in range(high.bit_length() - 1, -1, -1):
if high >> i & 1 == 0:
continue
# 如果这一位填 0，那么后面可以随便填
# 问题变成在 i 个位置中填 k 个 1 的方案数，满足 ones + k 是质数
for p in primes:
k = p - ones # 剩余需要填的 1 的个数
if k > i:
break
if k >= 0:
res += comb(i, k)
# 这一位填 1，继续计算
ones += 1
return res
def countPrimeSetBits(self, left: int, right: int) -> int:
return self.calc(right) - self.calc(left - 1)
MX = 20
comb = [[0] * MX for _ in range(MX)]
for i in range(MX):
comb[i][0] = 1
for j in range(1, i + 1):
comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j]
primes = [2, 3, 5, 7, 11, 13, 17, 19]
class Solution:
def calc(self, high: int) -> int:
# 转换成计算 < high + 1 的合法正整数个数
# 这样转换可以方便下面的代码把 high 也算进来
high += 1
res = ones = 0
for i in range(high.bit_length() - 1, -1, -1):
if high >> i & 1 == 0:
continue
# 如果这一位填 0，那么后面可以随便填
# 问题变成在 i 个位置中填 k 个 1 的方案数，满足 ones + k 是质数
for p in primes:
k = p - ones # 剩余需要填的 1 的个数
if k > i:
break
if k >= 0:
res += comb[i][k]
# 这一位填 1，继续计算
ones += 1
return res
def countPrimeSetBits(self, left: int, right: int) -> int:
return self.calc(right) - self.calc(left - 1)
class Solution {
private static final int MX = 20;
private static final int[][] comb = new int[MX][MX];
private static final int[] primes = {2, 3, 5, 7, 11, 13, 17, 19};
private static boolean initialized = false;
// 这样写比 static block 快
public Solution() {
if (initialized) {
return;
}
initialized = true;
// 预处理组合数
for (int i = 0; i < MX; i++) {
comb[i][0] = 1;
for (int j = 1; j <= i; j++) {
comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
}
}
}
public int countPrimeSetBits(int left, int right) {
return calc(right) - calc(left - 1);
}
private int calc(int high) {
// 转换成计算 < high + 1 的合法正整数个数
// 这样转换可以方便下面的代码把 high 也算进来
high++;
int res = 0;
int ones = 0;
for (int i = 31 - Integer.numberOfLeadingZeros(high); i >= 0; i--) {
if ((high >> i & 1) == 0) {
continue;
}
// 如果这一位填 0，那么后面可以随便填
// 问题变成在 pos 个位置中填 k 个 1 的方案数，满足 ones + k 是质数
for (int p : primes) {
int k = p - ones; // 剩余需要填的 1 的个数
if (k > i) {
break;
}
if (k >= 0) {
res += comb[i][k];
}
}
ones++; // 这一位填 1，继续计算
}
return res;
}
}
constexpr int MX = 20;
int comb[MX][MX];
auto init = [] {
// 预处理组合数
for (int i = 0; i < MX; i++) {
comb[i][0] = 1;
for (int j = 1; j <= i; j++) {
comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
}
}
return 0;
}();
class Solution {
static constexpr int primes[] = {2, 3, 5, 7, 11, 13, 17, 19};
int calc(int high) {
// 转换成计算 < high + 1 的合法正整数个数
// 这样转换可以方便下面的代码把 high 也算进来
high++;
int res = 0, ones = 0;
for (int i = bit_width((uint32_t) high) - 1; i >= 0; i--) {
if ((high >> i & 1) == 0) {
continue;
}
// 如果这一位填 0，那么后面可以随便填
// 问题变成在 i 个位置中填 k 个 1 的方案数，满足 ones + k 是质数
for (int p : primes) {
int k = p - ones; // 剩余需要填的 1 的个数
if (k > i) {
break;
}
if (k >= 0) {
res += comb[i][k];
}
}
ones++; // 这一位填 1，继续计算
}
return res;
}
public:
int countPrimeSetBits(int left, int right) {
return calc(right) - calc(left - 1);
}
};
const mx = 20
var comb [mx][mx]int
var primes = []int{2, 3, 5, 7, 11, 13, 17, 19}
func init() {
// 预处理组合数
for i := range comb {
comb[i][0] = 1
for j := 1; j <= i; j++ {
comb[i][j] = comb[i-1][j-1] + comb[i-1][j]
}
}
}
func calc(high int) (res int) {
// 转换成计算 < high + 1 的合法正整数个数
// 这样转换可以方便下面的代码把 high 也算进来
high++
ones := 0
for i := bits.Len(uint(high)) - 1; i >= 0; i-- {
if high>>i&1 == 0 {
continue
}
// 如果这一位填 0，那么后面可以随便填
// 问题变成在 i 个位置中填 k 个 1 的方案数，满足 ones + k 是质数
for _, p := range primes {
k := p - ones // 剩余需要填的 1 的个数
if k > i {
break
}
if k >= 0 {
res += comb[i][k]
}
}
// 这一位填 1，继续计算
ones++
}
return res
}
func countPrimeSetBits(left, right int) int {
return calc(right) - calc(left-1)
}
复杂度分析
不计入预处理的时间和空间。
- 时间复杂度：$\mathcal{O}\left(\dfrac{\log^2 \textit{right}}{\log\log \textit{right}}\right)$。循环 $\mathcal{O}(\log \textit{right})$ 次，每次循环会遍历 $\mathcal{O}(\log \textit{right})$ 以内的质数，根据质数密度，这有 $\mathcal{O}\left(\dfrac{\log \textit{right}}{\log\log \textit{right}}\right)$ 个。预处理组合数后，计算组合数的时间为 $\mathcal{O}(1)$。
- 空间复杂度：$\mathcal{O}(1)$。
专题训练
- 动态规划题单的「十、数位 DP」。
- 数学题单的「§2.2 组合计数」。
分类题单
如何科学刷题？
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
- 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
我的题解精选（已分类）
登录
{:width="350px"}{:align="left"}
