C++ 中的有害数字

在本文中，我们将讨论 C++ 中的有害数。

什么是有害数？

如果一个正数，其二进制展开中设置位的数量是**素数**，则该数被视为**有害数**。**3** 是第一个有害数，因为它等于**(11)**2。在 3 的二进制表示中，有两个设置位，其中**2**是一个**素数**。

前十个有害数是：**3, 5, 6, 7, 9, 10, 11, 12, 13, 14**。

性质

1. 任何 2 的幂都不是有害数，因为 2 的幂在二进制表示中是一个 1 后跟零。也就是说，1 不被认为是素数。
2. 由于二进制形式中有两个 1（是素数），所以任何形式为 2^n + 1 且 n > 0 的数都是有害数。
3. 一种被称为梅森数（Mersenne number）的有害数是以下形式之一：2^p - 1，其中 p 是素数。

例如

输入

• 12

输出

• 有害数。
• 二进制展开：1100
• 这里有两个设置位，2 是一个素数。
• 因此，12 是一个有害数。

输入

• 21

输出

• 有害数。
• 二进制展开：10101
• 这里有三个设置位，3 是一个素数。
• 因此，21 是一个有害数。

输入

• 32

输出

• 不是有害数。
• 二进制展开：100000 (2^5)。
• 这里只有一个设置位，1 不是一个素数。
• 32 不是一个素数。

示例

让我们用 C++ 程序来检查给定数字是否是有害数：-

输出

说明

计算设置位 (countSetBits)

• **countsetBits** 函数将确定一个数值为 1 的数字的二进制表示中有多少个设置位。
• 此函数遍历整数的每个位，并确定它是否是设置位，并相应地增加计数。
• 可以将数字高效地向右移位以验证每个位，直到该数字等于 0。
• 最终返回设置位的计数。

检查素数 (isPrime 函数)

• 此函数可用于计算数字的素数因子。
• 为了首先处理常见情况，如果数字小于或等于 1，则返回 false。如果值为 2 或 3，则返回 true。
• 接下来，它验证任何其他数字的素数性。它遍历从 5 到数字平方根的所有可能除数。
• 它确定给定数字是否可被其下一个奇数邻居 (i + 2) 或其当前除数 (i) 整除。如果可以，则返回 false。
• 如果没有发现除数，则返回 true，这意味着该数字是素数。

检查有害性 (isPernicious 函数)

• 此函数验证给定数字是否是有害数。
• 使用**countSetBits**函数，它首先确定输入数字二进制表示中设置位的数量。
• 之后，使用**isPrime**函数来确定该计数是否为素数。
• 如果设置位的计数是素数，则返回 true，这意味着该数字是有害数。否则，返回 false。

复杂度分析

时间复杂度

• 查找给定数字是否为有害数的时间复杂度为 **O(log n + sqrt(n))**。

空间复杂度

• 查找给定数字是否为有害数的空间复杂度为 **O(1)**，因为没有使用辅助空间。