零、写在前面

  这是《算法零基础100讲》 专栏打卡学习的第十二天了。
  在刷题的过程中，总结自己遇到的坑点，写出 「 解题报告 」 供他人学习，也是一种自我学习的方式。这就是经典的帮助他人的同时，成就自己。目前， 「 万人千题 」 社区 每天都会有五六篇高质量的 「 解题报告 」 被我 「 加精 」。如果觉得自己有能力的，也可以来发布你的 「 解题报告 」。千万级流量，你我共同拥有。

一、概念定义

  如何求一个数 $n$ 的因子和呢？
  考虑数 $n$，令 $n$ 的因子和为 $s(n)$，对 $n$ 进行素数分解后的，假设最小素数为 $p$，素因子 $p$ 的个数为 $e$ ，那么

$$n = p^en'$$

  容易得知，当 $n$ 的因子中 $p$ 的个数为 $0$ 时，因子之和为 $s(n')$。更加一般地，当 $n$ 的因子中 $p$ 的个数为 $k$ 的时候，因子之和为 $p^k * s(n')$，所以 $n$ 的所有因子之和就可以表示成：

$$\begin {aligned} s(n) &= (p^0 + p^1 + p^2 + ... p^e) * s(n') \\ &= \frac {p^{e+1} - 1} {p-1} * s(n') \end {aligned}$$

   $s(n')$ 可以通过相同方法递归计算。最后可以表示成一系列等比数列和的乘积。如下：

$$s(n) =\prod_{i=1}^k \frac {p_i^{e_i+1} - 1} {p_i-1}$$

二、题目描述

  给定一个 $n(n \le 10^4)$ 个整数的数组 $nums$，元素的范围小于等于 $10^5$ 的正整数，请你返回该数组中恰有四个因数的这些整数的各因数之和。

三、算法详解

  根据因子数的定义，有四个因子数的数，有两种情况：
    1）两个素数的乘积，即 $x=pq$；
    2）某个素数的三次幂，即 $x=p^3$；
  所以可以先对 10^5 内的所有的数进行素数筛选。然后遍历数组，对于每个数 $x$ ，进行 $[2, \sqrt x]$ 范围内的素数进行试除：
  如果能够分解成两个素数的乘积，则继续根据 因子和 的公式，计算因子和。具体的，如果 $x = pq$，则因子和为

$$\frac {p^2-1}{p-1} \frac {q^2-1}{q-1} = (p+1)(q+1)$$

  如果能够分解一个素数的三次幂，则计算公式为：

$$\frac {p^4-1}{p-1} = p^3+p^2+p+1$$

四、源码剖析

#define maxn 100001
#define ll long long

bool f[maxn];
int primes[maxn];

void ethPrime(){
    int i;
    ll j;                                       
    f[0] = f[1] = 1;
    primes[0] = 0;
    for(i = 2; i < maxn; ++i) {
        if(!f[i]) {
            primes[++primes[0]] = i;
            for(j = (ll)i * i; j < maxn; j += i) {
                f[j] = 1;
            }
        }
    }
}

bool isPrime(int x) {
    return !f[x];
}

int sumFourDivisors(int* nums, int numsSize){
    int i, j, p, q;
    int ans = 0;
    ethPrime();                                  // (1)
    for(i = 0; i < numsSize; ++i) {              // (2)
        for(j = 1; j <= primes[0]; ++j) {        // (3)
            p = primes[j];
            if(nums[i] % p == 0) {
                q = nums[i] / p;
                if( isPrime(q) && p != q) {
                    ans += (p+1)*(q+1);         // (4)
                }
                if( q == (long long)p * p ) {
                    ans += p*p*p + p*p + p + 1; // (5)
                }                
                break;
            }
        }
    }
    return ans;
}

• $(1)$ 基本上数论的题，都离不开 素数筛选；
• $(2)$ 枚举每个数 $x = nums[i]$；
• $(3)$ primes[0]记录了题目范围内的素数个数，枚举范围内的素数；
• $(4)$ 当一个数是 $x=pq$ 的形式，则它 因子和 为 $\frac {p^2-1}{p-1} \times \frac {q^2-1}{q-1}$；
• $(5)$ 当一个数是 $x = p^3$ 的形式，则它的 因子和 为 $\frac {p^4-1}{p-1}$；

五、推荐专栏

六、习题练习

请参考原文