C++ 节俭数

在数学中，一个正整数如果其素因数分解的位数少于该数字本身的位数，则称为节俭数。换句话说，节俭数是指其素因数分解的位数多于该数字实际位数的数字。

• 以数字 625 为例。
• 其素因数分解 5^4 有两位数。
• 数字 625 包含三位数。
• 数字 625 是节俭数，因为其素因数分解的位数（2）少于数字本身的位数（3）。

以下是节俭数的示例

1. 125： 125 的素因数分解是 5^3，有两位数。然而，125 有三位数。
2. 128： 128 的素因数分解是 2^7，有两位数。然而，128 有三位数。
3. 243： 243 的素因数分解是 3^5，有两位数。然而，243 有三位数。
4. 256： 256 的素因数分解是 2^8，有两位数。然而，256 有三位数。
5. 1024： 1024 的素因数分解是 2^10，有三位数。然而，1024 有四位数。

素数不是节俭数，因为在素数的位数等于其素因数分解的位数时，不考虑值为 1 的指数。

例如，19

数字 19 可以表示为 19^1，其中指数不会改变其素因数分解中的位数。

数字 19 有 2 位数：1 和 9。

19 的素因数分解就是 19 本身，它也有 2 位数：1 和 9。

因此，数字 (19) 的位数等于其素因数分解 (19) 的位数。

节俭数可能是一系列数学谜题、竞赛和娱乐数学活动中有趣的挑战或关注点。它们提供了关于数字结构和素因数分布的信息。

通过研究节俭数，可以更深入地理解素因数分解以及不同数字表示之间的相互作用。此外，节俭数可能在密码学和编码理论中有所帮助，其中算法的创建和优化依赖于素因数和位数的操作。

示例

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

输出

 
Please enter a number to check whether the given number is a frugal or not: 243
243 is a frugal number.   

说明

这个 C++ 程序检查给定数字是否为节俭数。前两个函数用于计算数字素因数分解中的位数，它们是 counting_TheDigits_OfPrimeFactorization 和 countingTheDigits..

isFrugalNumber 函数计算给定数字的位数和素因数分解。接下来，它确定输入数字的位数是否严格大于输入数字的素因数的数量。如果满足前一个条件，则返回 true，表示该数字是节俭数。否则，返回 false。

主函数在提示用户输入数字后，计算输入数字的位数及其素因数分解的位数。比较这些计数并打印出该数字是否为节俭数。

复杂度分析

时间复杂度： 总时间复杂度为 O(n * log(logn))。 必须确定每个数字的素因数分解，这可以在 O(log(logn)) 的时间复杂度内完成。

空间复杂度： 每个数字都需要存储其素因数分解。在最坏的情况下，它将使用 O(n) 空间，其中每个数字都是节俭数。