突破PHP整数上限：PHP-Data-Structure-and-Algorithms中BigInteger大数运算与素数筛法实现

突破PHP整数上限PHP-Data-Structure-and-Algorithms中BigInteger大数运算与素数筛法实现【免费下载链接】PHP-Data-Structure-and-AlgorithmsA repository with implementations of different data structures and algorithms using PHP项目地址: https://gitcode.com/gh_mirrors/ph/PHP-Data-Structure-and-Algorithms在 PHP-Data-Structure-and-Algorithms 项目中BigNumber.php 的 BigInteger 类用数字数组模拟上万位大数完整实现大数加、减、乘、除、阶乘与幂运算彻底突破 PHP 64 位整数的上限同目录的 Sieve.php 则用埃拉托斯特尼筛法素数筛法一次筛出百万级素数。本文将带你通俗理解这两套数论神器的实现原理与运行方法。为什么 PHP 需要大数运算先说结论PHP 的 int 是有天花板的。环境整数上限大约能表示多大32 位 PHP2,147,483,647约 21 亿64 位 PHP9,223,372,036,854,775,807约 922 京19 位一旦计算结果超过这个值PHP 会自动退化为浮点数精度直接丢失。比如算100!100 的阶乘结果有 158 位原生整数完全放不下。常见场景包括 密码学与 RSA 加密中的超大质数计算 金融、科学计算中的高精度运算 算法竞赛中的阶乘、组合数问题这就是突破 PHP 整数上限的意义所在。BigInteger 大数运算核心设计思路实现代码在 BigNumber.php 中核心类BigInteger的设计非常直观——像小学生一样列竖式。1. 数字数组把每一位数字拆开存BigInteger 不使用原生 int 存数值而是把每一位数字存进数组const MAXDIGITS 10000; // 最多支持 1 万位数字 public $digits; // 每一位数字个位、十位…… public $lastDigit; // 最高位下标 public $signBit; // 符号位1 正 / -1 负可以看到 MAXDIGITS 10000意味着它最多能表示10000 位的整数——是 64 位整数上限的 500 多倍。构造器 __construct 会把字符串123拆成digits [3, 2, 1]个位在前方便从低位开始算进位。2. 加法与减法竖式进位/借位加法add()从个位向高位逐位相加满 10 进位符号不同的两个数相加会转化为减法处理。减法subtract()先用 compare() 比较大小不够减就借位相当于竖式里的向前借一并自动处理负数结果。这两个方法的时间复杂度都是O(位数)和大数规模成正比非常高效。3. 乘法与除法shift 移位是关键乘法multiply()模拟手算竖式乘法——先算出每一层的部分积再通过 shift()乘以 10 的 d 次方即整体左移对齐数位最后逐层相加。除法divide()从高位向低位逐位试商反复用被除数减去除数直到不够减为止得到商与余数的每一位。4. 阶乘与幂运算一次搞定天文数字两个杀手级工具方法方法位置能力示例阶乘 factorial()循环连乘100!共 158 位轻松算出幂运算 power()循环连乘55^5这类大幂次文件末尾 第 281–307 行 是自带的演示代码依次演示了大数加、减、乘、除、55 的 5 次方和100!直接运行就能看到完整结果php Algorithms/Numbers-Maths/BigNumber.php素数筛法一次找出所有素数BigNumber 解决大筛法解决多——想批量找出 2 到 n 之间的所有素数逐个数试除太慢而埃拉托斯特尼筛法的思路极其巧妙从 2 开始把每个素数的所有倍数划掉剩下的就是素数。核心实现见 sieveOfEratosthenes()$prime array_fill(0, $n 1, true); // 先假设都是素数 for ($p 2; $p * $p $n; $p) { // 只需筛到 sqrt(n) if ($prime[$p] true) { for ($i $p * 2; $i $n; $i $p) $prime[$i] false; // 划掉 p 的所有倍数 } }核心循环 只有短短几行但有两个精妙的优化点只筛到 √n任何合数 n 至少有一个不超过 √n 的因子所以外层循环到p * p n即可。从 2p 开始划掉p 本身是素数从第一个倍数p * 2开始标记即可。其时间复杂度约为O(n log log n)筛 500 万个数在普通机器上不到一秒。文件末尾 第 29 行 直接运行了sieveOfEratosthenes(5000000)会输出 500 万以内的全部 348,513 个素数。如何运行这个项目整个仓库零依赖克隆后直接运行即可git clone https://gitcode.com/gh_mirrors/ph/PHP-Data-Structure-and-Algorithms cd PHP-Data-Structure-and-Algorithms php Algorithms/Numbers-Maths/BigNumber.php # 运行大数运算演示 php Algorithms/Numbers-Maths/Sieve.php # 运行素数筛法演示项目要求 PHP 7依赖信息见 composer.json。学习路线顺藤摸瓜读完这两个文件建议沿 Algorithms/ 目录继续探索把数学 数据结构串成一条学习链 大数运算的进阶 → 查看同目录下的 Sieve.php 与 BigNumber.php理解数组模拟思想 递归基础 → Fibonacci.php 与 FibonacciMemoized.php斐波那契与记忆化 贪心与编码 → GreedyHuffmanEncoding.phpHuffman 编码同样依赖最小值优先思想️ 数据结构基础 → 从 DS/LinkedList/Classes/LinkedList.php、DS/Stack/Classes/Stack.php 起步再看 DS/Heap/Classes/MaxHeap.php 完整主题清单 → 项目 README.md 中列出了链表、树、图、排序等全部模块总结模块解决的问题核心思想关键代码位置BigInteger突破 PHP 整数上限数组存每一位 竖式进位BigNumber.php素数筛法批量高效求素数标记法划去合数Sieve.php两大亮点值得记住BigInteger 用小学生竖式实现了上万位整数的完整四则运算复杂度线性可控素数筛法用 O(n log log n) 一次筛出 500 万内所有素数。两者都只有不到 300 行代码是学习 PHP 算法思维的高性价比起点。【免费下载链接】PHP-Data-Structure-and-AlgorithmsA repository with implementations of different data structures and algorithms using PHP项目地址: https://gitcode.com/gh_mirrors/ph/PHP-Data-Structure-and-Algorithms创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考