C++ 中的完美总计数

引言

完美欧拉函数数 是一个正整数 n，其所有迭代欧拉函数（包括 n 本身）之和等于 n。这个概念将欧拉函数 (ϕ(n)) 与累加迭代结果直到值为 1 的思想相结合。

欧拉函数 ϕ(n) 统计小于 n 且与 n 互质的整数的数量。例如，ϕ(9)=6，因为 1、2、4、5、7 和 8 与 9 互质。

判断一个数是否是完美欧拉函数数的步骤

1. 使用 ϕ(n) 计算 n 的欧拉函数。
2. 继续计算结果的欧拉函数，直到达到 1。
3. 将所有中间结果（包括 n）相加。
4. 检查和是否等于 n。如果为真，则 n 是一个完美欧拉函数数。

示例

让我们以一个例子来说明 C++ 中的完美欧拉函数数。

输出

Enter a number: 9
9 is not a Perfect Totient Number.   

说明

1. 欧拉函数定义
   • 欧拉函数，表示为 ϕ(n)，计算小于 n 且与 n 互质的整数的数量。
   • 互质整数除 1 之外不与 n 共享任何公约数。
   • 欧拉函数是通过迭代 n 的素因数来实现的
   • 如果 p 是 n 的素因数，那么 p 的贡献通过公式 n x (1-1/p) 从 n 中减去。
2. 欧拉函数计算的迭代过程
   • 代码从给定的数字 n 开始，并重复应用欧拉函数，直到 n 变为 1。
   • 欧拉函数的每个结果都添加到累积和中。
   • 此过程确保所有中间结果以及原始数字都包含在和中。
   例如
   • 对于 n=9
   • ϕ(9)=6 (与 9 互质的数字是 1、2、4、5、7、8)。
   • ϕ(6)=2 (与 6 互质的数字是 1、5)。
   • ϕ(2)=1 (只有 1 与 2 互质)。
3. 累加迭代欧拉函数
   • 在计算每个欧拉函数后，程序将其添加到累积和变量中。
   • 一旦欧拉函数达到 1，迭代过程停止。
   • 最后，将原始数字 n 添加到累积和中，以确保所有值都被考虑。
4. 检查完美欧拉函数条件
   • 程序将累积和与原始数字 n 进行比较。
   • 如果和等于 n，则该数字是完美欧拉函数数。
   • 否则，它不是。
   例如
   • 对于 n=9
   • 欧拉函数序列：9,6,2,1。
   • 和：9+6+2+1=18。
   • 由于 18≠9，所以 9 不是一个完美欧拉函数数。
5. 用户输入和输出
   • 程序从用户那里获取一个整数输入。
   • 它应用上述过程来确定该数字是否是完美欧拉函数数。
   • 结果以消息形式显示，指示输入是否满足条件。

通过示例理解

情况 1：输入 = 3

• ϕ(3)=2, ϕ(2)=1。
• 和：3+2+1=6。
• 6≠3，所以 3 不是完美欧拉函数数。

情况 2：输入 = 27

• ϕ(27)=18, ϕ(18)=6, ϕ(6)=2, ϕ(2)=1。
• 和：27+18+6+2+1=54。
• 54≠27，所以 27 不是完美欧拉函数数。

情况 3：输入 = 35

• ϕ(35)=24, ϕ(24)=8, ϕ(8)=4, ϕ(4)=2, ϕ(2)=1。
• 和：35+24+8+4+2+1=74。
• 74≠35，所以 35 不是完美欧拉函数数。

复杂度分析

时间复杂度

欧拉函数计算： O(√n) 用于查找素因数。

迭代次数： O(log(n)) 因为 n 的值随着每次欧拉函数计算而减小。

总时间复杂度： O(√n.log(n))。

空间复杂度

该算法使用少量变量来存储中间结果，例如当前数字、和以及欧拉函数值。

总空间复杂度： O(1)（常数空间），因为没有使用额外的数据结构。

性质

C++ 中完美欧拉函数数的几个属性如下：

自引用性质

• 完美欧拉函数数是自引用的，因为它的总值与欧拉函数的累积行为相平衡。
• 与其他数字不同，完美欧拉函数数精确地匹配它们的初始值，而其他数字要么超过其迭代欧拉函数和，要么低于其迭代欧拉函数和。

欧拉函数值递减

• 欧拉函数 ϕ(n) 在每一步都会减小 n 的值
• n>ϕ(n)>ϕ(ϕ(n))>⋯>1
• 这种减少是因为 ϕ(n) 计数与 n 互质的整数，这些整数总是少于 n 本身。
• 该过程保证在有限步数后终止于 1。