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

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

问题描述

给你两个整数left和right，请你找到在[left, right]范围内，计算置位位数为质数的整数个数。

• 计算置位：指二进制表示中 1 的个数。
• 质数：大于 1 且只能被 1 和自身整除的数。

注意：1 不是质数。

示例：

输入: left = 6, right = 10 输出: 4 解释: 6 -> 110 (2 个计算置位，2 是质数) 7 -> 111 (3 个计算置位，3 是质数) 8 -> 1000 (1 个计算置位，1 不是质数) 9 -> 1001 (2 个计算置位，2 是质数) 10-> 1010 (2 个计算置位，2 是质数) 共计 4 个整数拥有质数个计算置位。

算法思路

关键：

1. 范围限制：约束1 <= left <= right <= 10^6
2. 最大位数：10^6 < 2^20，所以任何数字的二进制表示最多有 20 位
3. 质数范围：计算置位的个数范围是 [1, 20]，所以只需要判断 1-20 中的质数

预处理优化：

• 在 [1, 20] 范围内的质数只有：2, 3, 5, 7, 11, 13, 17, 19
• 可以预先将这些质数存储在 Set 中，避免重复的质数判断

代码实现

方法一：预处理质数 + 位运算计数

importjava.util.*;classSolution{/** * 计算在[left, right]范围内计算置位位数为质数的整数个数 * * @param left 范围左边界（包含） * @param right 范围右边界（包含） * @return 满足条件的整数个数 */publicintcountPrimeSetBits(intleft,intright){// 预处理[1, 20]范围内的质数// 由于10^6 < 2^20，所以最多有20个1Set<Integer>primes=newHashSet<>(Arrays.asList(2,3,5,7,11,13,17,19));intcount=0;// 遍历范围内的每个数字for(intnum=left;num<=right;num++){// 计算二进制表示中1的个数intsetBits=countSetBits(num);// 检查1的个数是否为质数if(primes.contains(setBits)){count++;}}returncount;}/** * 计算整数二进制表示中1的个数（计算置位） * * @param n 待计算的整数 * @return 二进制中1的个数 */privateintcountSetBits(intn){intcount=0;// 使用位运算：每次清除最低位的1while(n!=0){n=n&(n-1);// 清除最低位的1count++;}returncount;}}

方法二：使用内置函数

importjava.util.*;classSolution{/** * 使用Java内置函数 * * @param left 范围左边界 * @param right 范围右边界 * @return 满足条件的整数个数 */publicintcountPrimeSetBits(intleft,intright){// 预处理质数集合Set<Integer>primes=Set.of(2,3,5,7,11,13,17,19);intcount=0;for(intnum=left;num<=right;num++){// 使用Integer.bitCount()计算1的个数if(primes.contains(Integer.bitCount(num))){count++;}}returncount;}}

方法三：手动质数判断

classSolution{/** * 不使用预处理，每次动态判断质数 * * @param left 范围左边界 * @param right 范围右边界 * @return 满足条件的整数个数 */publicintcountPrimeSetBits(intleft,intright){intcount=0;for(intnum=left;num<=right;num++){intsetBits=Integer.bitCount(num);if(isPrime(setBits)){count++;}}returncount;}/** * 判断一个数是否为质数 * * @param n 待判断的数 * @return true表示是质数，false表示不是 */privatebooleanisPrime(intn){// 1不是质数，小于1的数也不是质数if(n<2){returnfalse;}// 2是质数if(n==2){returntrue;}// 偶数不是质数if(n%2==0){returnfalse;}// 只需检查到sqrt(n)for(inti=3;i*i<=n;i+=2){if(n%i==0){returnfalse;}}returntrue;}}

算法分析

• 时间复杂度：O(n × log m)

  • n = right - left + 1（范围内的数字个数）
  • log m = 计算每个数字1的个数的时间（m为数字大小）
  • 方法一和二由于预处理质数，质数判断为O(1)
  • 方法三的质数判断为O(√k)，k≤20，也是O(1)

• 空间复杂度：

  • 方法一、二：O(1) - 质数集合大小固定（8个元素）
  • 方法三：O(1) - 无额外空间

算法过程

输入：left = 6, right = 10

逐个分析：

1. num = 6：

   • 二进制：110
   • 1的个数：2
   • 2是质数

2. num = 7：

   • 二进制：111
   • 1的个数：3
   • 3是质数

3. num = 8：

   • 二进制：1000
   • 1的个数：1
   • 1不是质数

4. num = 9：

   • 二进制：1001
   • 1的个数：2
   • 2是质数

5. num = 10：

   • 二进制：1010
   • 1的个数：2
   • 2是质数

总计：4个满足条件的数字

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例System.out.println("Test 1: "+solution.countPrimeSetBits(6,10));// 4// 测试用例2：包含1的情况System.out.println("Test 2: "+solution.countPrimeSetBits(1,5));// 2// 1->1(1个1,非质数), 2->10(1个1,非质数), 3->11(2个1,质数), 4->100(1个1,非质数), 5->101(2个1,质数)// 测试用例3：较大范围System.out.println("Test 3: "+solution.countPrimeSetBits(10,15));// 5// 10->1010(2), 11->1011(3), 12->1100(2), 13->1101(3), 14->1110(3), 15->1111(4非质数)// 测试用例4：边界情况System.out.println("Test 4: "+solution.countPrimeSetBits(1,1));// 0// 测试用例5：全范围System.out.println("Test 5: "+solution.countPrimeSetBits(1,1000000));// 大数值测试// 测试用例6：包含最大1个数的情况System.out.println("Test 6: "+solution.countPrimeSetBits(1048575,1048575));// 1048575 = 2^20-1 (20个1,非质数) -> 0// 测试用例7：验证质数边界System.out.println("Test 7: "+solution.countPrimeSetBits(2097151,2097151));// 2097151 = 2^21-1 (21个1,非质数) -> 0// 测试用例8：刚好20个1的数inttwentyOnes=(1<<20)-1;// 1048575System.out.println("Test 8: "+solution.countPrimeSetBits(twentyOnes,twentyOnes));// 0 (20不是质数)// 测试用例9：19个1的数intnineteenOnes=(1<<19)-1;// 524287System.out.println("Test 9: "+solution.countPrimeSetBits(nineteenOnes,nineteenOnes));// 1 (19是质数)}

关键点

1. 范围：

   • 10^6 < 2^20 = 1,048,576
   • 任何输入数字最多有20个1
   • 质数判断只需考虑1-20的范围

2. 质数集合：

   • [1, 20]内的质数：2, 3, 5, 7, 11, 13, 17, 19
   • 共8个质数

3. 位计数：

   • n & (n-1)：清除最低位的1，高效计数
   • Integer.bitCount()：Java内置函数，底层优化

4. 质数定义：

   • 1不是质数
   • 质数必须大于1且只有1和自身两个正因数

常见问题

1. 为什么1不是质数？

   • 质数定义要求大于1且只有两个正因数
   • 1只有1个正因数（就是1本身）

2. 为什么可以预处理质数？

   • 由于输入范围限制，1的个数最多为20

3. 位计数？

   • 逐位检查：while(n > 0) {count += n & 1; n >>= 1;}
   • 内置函数：Integer.bitCount(n)
   • 查表法：预先计算0-255的位数