快速求约数(divisor)

一个通常情况足够快,且好写的求约数算法

算法描述

首先求质因数,复杂度为 sqrt(最大质因数) 将原数分解为多个质因数的乘积后,求约数的方法也很简单。 每各个不同 的质因数,将该质因数的不同次方和不含该质因子的已知约数相乘,合并到结果集中。

如分求 36 的约数,首先分解为 2 × 2 × 3 × 3

  1. 初始化,集合中仅有 [1] 一个约数
    此时结果集为[1]
  2. 将 2 和 4 分别和 [1] 相乘 得到 [2, 4], 合并
    此时结果集为[1, 2, 4]
  3. 将 3 和 9 分别和 [1, 2, 4] 相乘 得到 [3, 6, 12, 9, 18, 36] 合并
    此时结果集为[1, 2, 4, 3, 6, 12, 9, 18, 36]

实现

分解质因数和后面的过程可以合并执行,不需要记录质因子,最终代码如下

原创文章,转载请注明(最好把图片带走): 转载自Comzyh的博客

本文链接地址: 快速求约数(divisor)

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据