C++ 中的迪洛尔数

引言

数字具有迷人的属性，这使得它们成为数学和编程中的一个令人兴奋的话题。其中一个引人入胜的类别是趣味数字。在本文中，我们将探讨趣味数字是什么，定义它们的属性，并实现一个高效的C++ 程序来识别它们。

问题陈述

趣味数字是一个数字N，其偶数素数因子的和等于其奇数素数因子的和。

关键注意事项

在C++中，趣味数字的几个关键考虑因素如下：

1. 素数因子：一个数字的素数因子是完全整除它的素数。
2. 偶数素数因子：唯一的偶数素数是2。
3. 奇数素数因子：包括 3、5、7、11 等。
4. 趣味数字的条件:

所有偶数素数因子的和必须等于所有奇数素数因子的和。

示例

示例 1

N = 30

• 素数因子 2, 3, 5
• 偶数素数因子之和 2
• 奇数素数因子之和 3 + 5 = 8
• 由于 2 ≠ 8，30 不是趣味数字

示例 2

N = 42

• 素数因子 2, 3, 7
• 偶数素数因子之和 2
• 奇数素数因子之和 3 + 7 = 10
• 由于 2 ≠ 10，42 不是趣味数字

示例 3

N = 6

• 素数因子 2, 3
• 偶数素数因子之和2
• 奇数素数因子之和 3
• 由于 2 ≠ 3，6 不是趣味数字

示例 4

N = 72

• 素数因子 2, 2, 2, 3, 3
• 偶数素数因子之和 2+2+2 = 6
• 奇数素数因子之和 3+3 = 6
• 由于 6 = 6，72 是趣味数字

解决问题的方法

1. 求 N 的素数因子

• 使用试除法提取素数因子。

2. 对偶数和奇数素数因子进行分类

• 如果素数因子是 2，则将其添加到偶数素数因子之和中。
• 如果素数因子是奇数，则将其添加到奇数素数因子之和中。

3. 检查总和是否相等

• 如果偶数素数之和 == 奇数素数之和，则 N 是趣味数字。

程序 1

让我们以一个例子来说明 C++ 中的趣味数字。

输出

Enter a number:6272
Yes, it is a Droll Number.   

说明

1. 识别所有素数因子
   • 找到整除给定数字 N 的素数。
   • 示例：如果 N = 72，则其素数因子为 2 和 3。
2. 分离偶数和奇数素数因子
   • 偶数素数因子：只有 2（因为 2 是唯一的偶数素数）。
   • 奇数素数因子：所有其他素数（3、5、7 等）。
3. 计算总和
   • 将所有偶数素数因子的出现次数相加。
   • 将所有奇数素数因子的出现次数相加。
4. 比较总和
   • 如果偶数素数因子之和 = 奇数素数因子之和，则该数字是趣味数字。
   • 否则，它不是趣味数字。

程序 2

让我们再举一个例子来说明 C++ 中的趣味数字。

输出

Enter the number of test cases: 10
Enter a number: 88
88 is NOT a Droll Number
Enter a number: 99
99 is NOT a Droll Number
Enter a number: 1
1 is NOT a Droll Number
Enter a number: 22
22 is NOT a Droll Number
Enter a number: 72
72 is a Droll Number
Enter a number: 6727
6727 is NOT a Droll Number
Enter a number: 6289
6289 is NOT a Droll Number
Enter a number: 66
66 is NOT a Droll Number
Enter a number: 11111
11111 is NOT a Droll Number
Enter a number: 6272
6272 is a Droll Number   

说明

1. 素数分解 (getPrimeFactors)
   • 它提取一个数字的素数因子。
   • 首先，它会反复除以 2（偶数素数）。
   • 之后，它会检查小于等于 sqrt(num) 的奇数素数因子。
   • 如果剩余的 num 大于 2，它也是一个素数因子。
2. 对偶数和奇数素数因子求和 (calculateSums)
   • 它遍历素数因子列表。
   • 分别对偶数和奇数因子进行求和。
3. 趣味数字检查 (isDrollNumber)
   • 它计算素数因子及其总和。
   • 如果偶数和奇数素数因子的总和相等，则返回 true。
4. 用户输入和执行 (main)
   • 它接受来自用户的多个测试用例。
   • 它读取一个数字并检查它是否是趣味数字。

程序 3

让我们再举一个例子来说明 C++ 中的趣味数字。

输出

Enter a number: 72
72 is a Droll Number.   

说明

1. 使用 Pollard's Rho 算法（更快的因式分解）
   • 与基本的试除法（O(√N)）不同，Pollard's Rho 的因式分解复杂度接近 O(N^1/4)。
   • 它能有效地处理大数（高达 10^18），使其成为大数计算的理想选择。
2. 使用埃拉托斯特尼筛法预计算素数
   • 我们预先计算一百万以内的素数（O(N log log N)），而不是反复检查素数。
   • 这减少了重复的素数检查，并加快了执行速度。
3. 使用哈希映射进行高效的素数因式分解
   • 我们使用 unordered_map 来计算素数出现的次数，而不是将素数因子存储在 vector 中。
   • 这可以防止重复计算，从而将每个因子的时间复杂度降低到 O(log N)。
4. 用于加速执行的早期退出条件
   • 如果在因式分解过程中一个数字变成素数，我们会立即返回，避免不必要的检查。
   • 如果数字为 1 或不可分解，我们会提前返回以节省计算。
5. 高效处理大数
   • 它在模乘法中使用 __int128 来防止处理大数时的溢出问题。
   • 它允许程序在不发生整数溢出的情况下处理高达 10^18 的数字。

学习趣味数字的优势

在 C++ 中学习趣味数字有几个优势：

1. 提高解决问题的能力
   • 理解趣味数字涉及素数分解、循环、条件检查和数学逻辑。
   • 这有助于培养强大的分析思维和解决问题的能力，这在编程竞赛中至关重要。
2. 加强数论知识
   • 趣味数字的概念与素数和整除规则密切相关。
3. 在密码学和安全领域有用
   • 许多加密算法依赖于素数和因式分解（例如，RSA 加密）。
   • 理解趣味数字有助于掌握模运算和数学安全概念。
4. 有助于竞争性编程
   • 基于数字属性的问题经常出现在编码竞赛中（Codeforces、LeetCode、CodeChef 等）。
   • 趣味数字问题涉及高效的因式分解和求和计算，这是竞争性程序员的关键技能。
5. 高效的算法设计
   • 趣味数字算法提高了解决数学问题的效率，从而在素数相关算法中实现了更好的优化技术。
   • 这有助于设计更好的数学和计算模型。

趣味数字的应用

在 C++ 中，趣味数字有几个应用，如下所示：

1. 数学和数论研究
   • 趣味数字为数字的数学属性提供了有趣的见解。
   • 它们可用于发现新的数字序列和素数的属性。
2. 计算机科学和算法开发
   • 基于因式分解的算法广泛用于数据压缩、哈希和索引。
   • 理解趣味数字有助于优化因式分解算法。
3. 密码学和网络安全
   • 像 RSA 加密这样的加密技术依赖于素数分解。
   • 研究趣味数字可以加强对模运算和安全算法的理解。
4. 数字取证和数据完整性
   • 许多取证工具使用数学算法来验证数据的真实性。
   • 趣味数字的属性有助于检测大型数据集中的异常。
5. 编码面试和竞争性编程
   • 关于素数和数学总和的问题在 FAANG（Facebook、Amazon、Apple、Netflix、Google）的面试中很常见。
   • 掌握趣味数字有助于轻松应对基于数论的问题。

结论

总之，趣味数字引入了一种基于其偶数和奇数素数因子对数字进行分类的独特方法。这个问题是练习 C++ 中的数论、素数分解和逻辑思维的绝佳方式。