C++ 中的斯芬克斯数

在本文中，我们将讨论 C++ 中的球形数。在讨论 C++ 中的球形数之前，我们必须了解其步骤、示例、时间复杂度和空间复杂度。

C++ 中的球形数是什么？

一个正整数，并且是恰好三个不同素数乘积的整数称为球形数。例如，30 是一个球形数，因为它可以分解为三个不同的素数 2×3×5，依此类推。同样，42 (2×3×7)、66 (2×3×11) 和 70 (2×5×7) 是球形数的其他示例。这些数字之所以重要，是因为它们具有独特的因式分解性质，即恰好三个素因子构成了它们的组成。

它定义了一个球形数恰好有八个约数。当一个球形数进行素因子分解时，其素因子的所有可能组合（包括 1 和数字本身）都用于创建该数字的约数。例如，如果 n=p1×p2×p3 且 p1、p2、p3 是不同的素数，则 "𝑝1,2,𝑝3,𝑝1×𝑝2,𝑝1×𝑝3,𝑝2×𝑝3,𝑝1×𝑝2×𝑝3" 将是 n 的约数，总计恰好八个约数。

检查一个数字是否是球形数的步骤

1. 约数计数： 检查该数字是否恰好有八个约数是第一步。如果一个数字的约数多于或少于八个，则它不是球形数。消除非球形数最简单的方法就是使用此检查。
2. 素数验证： 下一步是验证前三个约数（1 之后）是否是唯一的素数，如果该数字恰好有八个约数。这些素数将是该数字的素因子。当然，如果所有三个都是素数，则该数字是球形数。
3. 以数字 30 为例
   30 恰好有八个约数，它们是 1、2、3、5、6、10、15 和 30。
   2、3 和 5 是这些约数中唯一的素数，这一事实证明 30 是一个球形数。
4. 相比之下，像 12 这样的数字
   即使 2 和 3 是素因子，12 也不能是球形数，因为它的约数是 1、2、3、4、6 和 12，只有六个约数。
   因此，我们首先检查约数计数以查看一个数字是否是球形数，如果它是 8，我们接下来确认前三个约数的素性。通过使用它们独特的素因子分解特性，此方法可确保我们正确识别球形数。

示例

让我们举一个例子来说明 C++ 中的球形数。

输出

 
Enter a number to check if it is a Sphenic number: 30
Yes, the number is a Sphenic number.   

说明

这个 C++ 程序确定给定数字是否恰好有三个不同的素数约数，或者是否是球形数。它首先使用埃拉托斯特尼筛法生成所有小于 1000 的素数，以在 isPrime 数组中识别非素数。checkSphenicNumber 函数计算输入数字的所有约数。如果一个数字恰好有八个约数，并且前三个是不同的素数（由 isPrime 数组确定），则该数字被视为球形数。在 main 函数中要求用户输入一个数字，然后将其发送给 checkSphenicNumber 并确定它是否满足球形数标准。

程序根据其结果输出该数字是否是球形数。一个数组用于存储每个数字的素数状态，并且程序有效地搜索素数及其约数。

复杂度分析

• 时间复杂度：O(p log p)：为了确定素数，筛法算法遍历每个小于 p 的素数，将倍数指定为非素数。这导致时间复杂度为 O(plogp)。
• 辅助空间：O(n)： isPrime 数组存储了每个小于 n 的整数（在此例中为 1000）的素数状态，导致辅助空间复杂度为 O(n)。因此，使用的空间量与输入范围的大小成正比。