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

梦里梦外; 2022-05-19 07:22 129阅读 0赞

给定两个整数 `L` 和 `R` ，找到闭区间 `[L, R]` 范围内，计算置位位数为质数的整数个数。

（注意，计算置位代表二进制表示中1的个数。例如 `21` 的二进制表示 `10101` 有 3 个计算置位。还有，1 不是质数。）

**示例 1:**

输入: L = 6, R = 10
    输出: 4
    解释:
    6 -> 110 (2 个计算置位，2 是质数)
    7 -> 111 (3 个计算置位，3 是质数)
    9 -> 1001 (2 个计算置位，2 是质数)
    10-> 1010 (2 个计算置位，2 是质数)

**示例 2:**

输入: L = 10, R = 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 不是质数)

**注意:**

1.  `L, R` 是 `L <= R` 且在 `[1, 10^6]` 中的整数。
2.  `R - L` 的最大值为 10000。

--------------------

思路：使用位运算找出整数的二进制中1的个数one\_count，再判断one\_count是否是质数。

class Solution {
        public int countPrimeSetBits(int L, int R) {
           //1.找出0~32中的质数
        	boolean flag[]=new boolean[33];
        	for(int i=0;i<32;i++) {
        		flag[i]=true;
        	}
        	for(int i=2;i<33;i++) {
        		if(flag[i]) {
        			for(int j=i+i;j<33;j+=i) {
        				flag[j]=false;
        			}
        		}
        	}
        	
        	int sum_count=0;//置位位数为质数的整数个数
        	for(;L<=R;L++) {
        		int one_count=0;//L的二进制数中1的个数
        		for(int i=0;i<32;i++) {
        			if((L>>i&1)==1) {
        				one_count++;
        			}
        		}
        		if(flag[one_count]&&one_count!=1) {
        			sum_count++;
        		}
        	}
        	return sum_count;
        }
    }