快速计算约数的个数——从基础到高级

全栈程序员-站长 • 2026年3月18日上午10:09 • 未分类 • 阅读 2

题目来源：【欧拉计划第 12 题】高度可除的三角数 Highly divisible triangular number

这道题我们在枚举完三角数后，最重要的是去判断何时某个三角数约数的个数大于 500

下面我们来看下，针对计算约数的个数问题，用不同的算法解决，逐步求得最优解

方法 1

最简单，更是非常容易理解的方法

复杂度： $\large O_{\left ( n^{2} \right )}$

主要思想：定义变量，使其在小于传入判断值的条件下从 1 开始自增，如果判断值和该变量进行模取运算后的值为 0，则说明该变量此时的值是判断值得一个约数。那么，程序计数器自增，记录下此值。循环结束后，输出计数器保存的值即为判断值约数的个数

这种方法优点除易于理解外，怕是没有优点了。缺点当然就是时间复杂度太高，一个值就需要去从 1 一直判断到该值。试想，如果数据量呈指数增长，这种方法恐怕在一般的计算机上不容易很快得到答案

实现代码如下

int check(long long n) { 
    int count = 0; long long i = 1; //注意数据范围 while (i <= n) { 
    if (n % i == 0) //成立,这说明此时 i 为 n 的一个约数 { 
    count++; //计数器自增 } i++; //继续判断下一个数字是否为 i 的约数 } return count; }

方法 2

复杂度： $\large O_{\left ( \sqrt{n} \right )}$

主要思想：对比可以看出，方法一和方法二差别不大，但影响最关键的是它们的复杂度，直接由 $O_{\left ( n^{2} \right )}$ 降至 $O_{\left ( \sqrt{n} \right )}$

同样，仍然是暴力枚举，只不过这里的判断条件由 i < = n 变为 i * i < = n，复杂度优化了些许。进入 for() 循环后，如果 n % i == 0 ，那么说明此时的 i 值是 n 的一个约数

大家在这里要注意的是 if...else 语句内容，这里主要解释下此处和方法一的差别

举个例子，如果 n = 4 ，i = 2，满足 2 × 2 = 4 的条件，但此时 4 的两个约数 2 相当于一个，程序计数器只能自增 1 ，而不是 2

当然，如果进入 for() 循环后，不满足条件 i * i = n ，那么自然是两个不同的约数，此时程序计数器需要增加 2，而不是 1

int check(long long n) { 
    int count = 0; for (long long i = 1; i * i <= n; i++) { 
    if (n % i == 0) { 
    if (i * i == n) // 区别所在,重点理解 count++; else count += 2; } } return count; }

方法 3

试除法求解

vector<int> get_divisors(int n) { 
    vector<int> res; for (int i = 1; i <= n / i; i++) if (n % i == 0) { 
    res.push_back(i); if (i != n / i) res.push_back(n / i); } sort(res.begin(), res.end()); return res; }

LeetCode 题解思路

方法四

约数个数定理

设一个数可以表示为其素数幂的乘积，即：

$\large n={p_{1}}^{e_{1}} \cdot {p_{2}}^{e_{2}} \cdot\cdot\cdot {p_{m}}^{e_{m}}$

则该数的约数个数为：

$\large \left ( e_{1}+1 \right )\cdot \left ( e_{2}+1 \right )\cdot \cdot \cdot \left ( e_{m}+1 \right )$

参考代码：

#include  
     using namespace std; int main() { 
    int N, n, i, s, r; while (scanf("%d", &N) != EOF) { 
    while (N--) { 
    cin >> n; s = 1; for (i = 2; i * i <= n; i++) { 
    r = 0; while (n % i == 0) { 
    r++; n /= i; } if (r > 0) { 
    r++; s *= r; } } if (n > 1) s *= 2; cout << s; } } return 0; }

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/217190.html原文链接：https://javaforall.net

快速计算约数的个数——从基础到高级

方法 1

方法 2

方法 3

方法四

关于作者

全栈程序员-站长

发表回复

快速计算约数的个数——从基础到高级

方法 1

方法 2

方法 3

方法四

关于作者

全栈程序员-站长

相关推荐

python中for循环语句例子_python怎么循环1到8不要4

标准网页两侧浮动广告代码,支持FF及IE

pytorch的安装及其在pycharm中的使用「建议收藏」

高并发下接口幂等性解决方案

谈谈我对证券公司一些部门的理解——前、中、后台（转）

莫比乌斯反演简单题

发表回复