C++ 中的皮尔庞特素数

引言

在数论中，皮尔庞特素数备受关注。以詹姆斯·皮尔庞特的名字命名，这些素数表示为 2^u ⋅ 3^v +1，其中 u ≥ 0 且 v ≥ 0。将此类素数称为不可约素数是常见且完全可以接受的。在可构造多边形及其与单位根的关系的背景下，它们特别引人入胜。我们将皮尔庞特素数定义为可以表示为 P(u, v) = 2^u ⋅ 3^v +1 的素数，其中 u、v 是任何非负整数。本文将重述皮尔庞特问题，描述一种查找 P(u, v) 形式值的算法，并演示一个 C++ 解决方案。

问题陈述

目标是在指定范围内查找皮尔庞特素数。更具体地说，我们旨在

1. 确定 2^u.3^v+1 形式的数字，其中 u 和 v 采用非负整数值。
2. 检查所得数字是否为素数。
3. 列出直到某个数字 N 的所有皮尔庞特素数。

此问题需要并考虑并行乘法和素数验证，这使其成为改进算法设计和完善技能的完美候选者。

示例 1

让我们举一个例子来说明 C++ 中的皮尔庞特素数。

输出

Enter the upper limit: 1000
Pierpont primes up to 1000:
2 3 5 7 13 17 19 37 73 97 109 163 193 257 433 487 577 769   

代码解释

1. 素数检查： isPrime 函数使用简单的试除法，直到数字的平方根，以提高效率。
2. 幂次迭代： 外层循环迭代 2 的幂次，而内层循环处理 3 的幂次。一旦各自的幂次超过限制，两个循环都会终止。
3. 动态范围检查： 程序确保不超过限制的数字不会进一步计算，从而保持执行效率。

复杂度分析

1. 时间限制： 正确素数确定的复杂性将取决于 u 和 v 范围内的任何单位中未解决的因素。本质上，这些计算的数量决定了当前 T(n) 的时间设置。对于每个素数候选，时间界限为 O(√n)。
2. 计算空间应变： 程序中采用的 O(k) 型空间取决于生成的皮尔庞特定义素数的数量。

示例 2

让我们再举一个例子来说明 C++ 中的皮尔庞特素数。

输出

Enter the upper limit for Pierpont primes: 1000000
Enter the number of threads to use: 4
Pierpont primes up to 1000000:
2 3 5 7 13 17 19 37 73 97 109 163 193 257 433 487 577 769 1153 1297 1459 2593 2917 3457 3889 10369 12289 17497 18433 39367 52489 65537 139969 147457 209953 331777 472393 629857 746497 786433 839809 995329 
Execution time: 0.00244984 seconds   

此代码的特点

1. Miller-Rabin 素性测试
   • 一种更高效的概率素性测试，可以处理大数字。
   • 它提供适用于大多数实际应用的准确性。
2. 多线程
   • 它使用线程通过在多个线程之间划分 u 值的范围来分担工作负载。
   • 它使用互斥锁确保结果的线程安全收集。
3. 动态资源分配
   • 用户可以指定线程数，从而实现可用 CPU 内核的最佳利用。
4. 性能优化
   • 它结合了 2 的幂次的位操作 (1<<u) 和动态范围检查以提高效率。
   • 它消除了重复结果并对最终输出进行排序。

复杂度分析

1. 时间复杂度
   • Miller-Rabin 测试：O(k⋅log3(n))，其中 k 是迭代次数，n 是候选数字。
   • 总体复杂性取决于 u 和 v 的范围以及并行化。
2. 空间复杂度
   • 结果向量的大小和线程堆栈大小决定了内存使用量。

结论

本文介绍了可用于查找皮尔庞特素数的有效算法。在本文中，C++ 用于说明如何将理论概念转换为功能框架。皮尔庞特素数不仅是一个有趣的数学概念，而且还是深入研究更复杂的数论概念的工具。