求整数的约数个数

题目

三角形数数列是通过逐个加上自然数来生成的。例如，第7个三角形数是 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28。三角形数数列的前十项分别是：

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
让我们列举出前七个三角形数的所有约数：

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
我们可以看出，28是第一个拥有超过5个约数的三角形数。

第一个拥有超过500个约数的三角形数是多少？

涉及知识点

约数个数定理

任意一个整数N分解质因数，均可以表示为如下形式：$N = \prod_{i=1}^n p_1^{a_1} * p_1^{a_1} * \cdots * p_n^{a_n}$N=i=1∏n​p1a1​​∗p1a1​​∗⋯∗pnan​​
则其约数个数 $F(N)$F(N)为：$F(N) = \prod_{i=1}^n (a_i + 1)$F(N)=i=1∏n​(ai​+1)
若A，B互素， 且 $C = A * B$C=A∗B ,则C的约数个数为：
$F(C) = F(A) * F(B)$F(C)=F(A)∗F(B)

题目分析

• 素数的只有1和它本身两个约数
• 利用上面的公式， 在线性筛标记合数的过程求出合数的约数个数

代码如下

#include<iostream>
using namespace std;

#define max_n 100000

int prime[max_n + 5] = {0};
int f[max_n + 5] = {0};
int cnt[max_n + 5] = {0};

void init() {
    for (int i = 2; i <= max_n; ++i) {
        if (!prime[i]) {
            prime[++prime[0]] = i;
            f[i] = 2; // 素数的约数只有两个
        }
        for (int j = 1; j <= prime[0]; j++) {
            if (i * prime[j] > max_n) break;
            prime[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                int a = i, cnt = 0;
                while (a % prime[j] == 0) a /= prime[j], cnt++; //cnt为旧合数的prime[j]因子的幂次
                f[i * prime[j]] = f[i] / (cnt + 1) * (cnt + 2); //新标记的合数和旧合数之间的因子满足这种关系
                break;
            } else {
                f[i * prime[j]] = f[i] * f[prime[j]]; // i和prime[j]互素
            }
        }
    }
    return;
}

int main() {
    init();
    long long f_max = 0, n = 1;
    while (1) {
        if (n & 1) {
            f_max = f[n] * f[(n + 1) >> 1];
        } else {
            f_max = f[n >> 1] * f[n + 1];
        }
        if (f_max > 500) break;
        n += 1;
    }
    cout << n * (n + 1) / 2 << " = " << n;

    return 0;
}