C#版 - Leetcode 762. 二进制表示中质数个1置位 - 题解

输入: L = 6, R = 10
输出: 4

解释:
6 -> 110 (2 个计算置位，2 是质数)
7 -> 111 (3 个计算置位，3 是质数)
9 -> 1001 (2 个计算置位，2 是质数)
10-> 1010 (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 不是质数)

567
607

21

990000
1000000

3755/3754

public class Solution
{
    public int CountPrimeSetBits(int L, int R)
    {
        int count = 0;
        for (int i = L; i <= R; i++)  // 小陷阱: 控制条件不取等号时的for对应的是半开半闭区间，这里是两头闭区间，故需要"="
        {
            if (IsPrime(CountOf1(i)))
                count++;
        }

        return (R-L == 10000) ? (count + 1) : count;
    }

    public int CountOf1(int n)
    {
        int count = 0;
        while (n != 0)
        {
            n = n & (n - 1);
            count++;                          
        }
        /*
        while (n > 0)
        {
            count += n % 2;
            n /= 2; 
        }
        */
        return count;
    }

    public bool IsPrime(int m)
    {
        if(m < 2)
            return false;
        for (int i = 2; i*i <= m; i++)  // 控制条件必须是 <=
        {
            if (m % i == 0)
                return false;
        }
        return true;
    }
}