题目

链接

LeetCode 762[二进制表示中质数个计算置位]

详情

实例

提示

题解

思路

两个条件：

1、二进制位为1

2、满足条件1的个数为质数

 首先 for 循环遍历区间

        for (int i = left; i < right + 1; i++)
        {
            int iCount = 0;//二进制位为1的个数
            int iNum = i;//待转换成二进制的数
            ...
        }

以下为for 循环的循环体：

求 iNum 二进制位并求出二进制位为1的个数 iCount：

常规方法就是 iNum 不停的循环除2，然后它的余数就是二进制位了，当其余数为1时，iCount 加1，直到最后得到的商为0，就退出循环

            while (iNum > 0)
            {
                if (1 == (iNum % 2))
                    iCount++;

                iNum /= 2;
            }

再判断 iCount 是否为质数，为质数则返回值 iRet 加1

            if (is_Prime(iCount))
                iRet++;

遍历结束后输出 iRet

        return iRet;

此处写了一个 is_Prime 函数用来判断是否为质数：

首先判断传入值 num 是否为 0，为 0 则不为质数，输出false

        if (0 == iNum)
            return false;

然后判断传入值 num 是否为 1，为1则不为质数，输出false

        if (1 == iNum)
            return false;

之后 for 循环来从 2 开始遍历，到 num - 1 循环结束，如果遍历值能被 num 整除，则不为质数，输出 false

        for (int i = 2; i < iNum; i++)
        {
            if (0 == iNum % i)
                return false;
        }

遍历结束，则除了 1 和 num 本身外，不能整除，则为质数，输出 true

        return true;

代码