【小航的算法日记】因子和

目录

• ​​一、概念​​
• ​​二、模板​​
• ​​三、例题​​

• ​​题：1390. 四因数​​
• ​​解：​​

一、概念

因子和

二、模板

看例题

三、例题

题：1390. 四因数

给你一个整数数组 ​​nums​​，请你返回该数组中恰有四个因数的这些整数的各因数之和。

如果数组中不存在满足题意的整数，则返回 ​​0​​ 。

示例：

输入：nums = [21,4,7]
输出：32
解释：
21 有 4 个因数：1, 3, 7, 21
4 有 3 个因数：1, 2, 4
7 有 2 个因数：1, 7
答案仅为 21 的所有因数的和。

提示：

1 <= nums.length <= 10^4
1 <= nums[i] <= 10^5

解：

解题思路：​​暴力枚举​​

AC代码：

class Solution {
    public int sumFourDivisors(int[] nums) {
        int ans = 0;
        for(int num : nums) {
            int factor_cnt = 0; // 因子个数
            int factor_sum = 0; // 因子和
            for(int i = 1; i * i <= num; i ++) {
                if(num % i == 0) {
                    factor_cnt ++;
                    factor_sum += i;
                    if(i * i < num) {
                        factor_cnt ++;
                        factor_sum += num / i;
                    }
                }
            }
            if(factor_cnt == 4) { // 如果因子个数等于4
                ans += factor_sum;
            }
        }
        return ans;
    }
}

解题思路：​​算数基本定理​​​ + ​​Eratosthenes筛选法​​

这里当因子数为4时：

(1) x = pq (p,q为素数) aj = 2，s = 2

(2) x = p³(p为素数) alj=3，s = 1

AC代码：

class Solution {
    static int MAX = 100001; 
    static int[] f = new int[MAX]; 
    static int[] primes = new int[MAX];// 质数表

    public int sumFourDivisors(int[] nums) {
        int ans = 0;      
        eth(); // 筛选素数
        for(int num : nums) {
            for(int i = 1; i <= primes[0]; i ++) { // 遍历质数表
                int p = primes[i];
                if(num % p == 0) {
                    int q = num / p;
                    if(f[q] == 0 && p != q) ans += (p + 1) * (q + 1);
                    if(q == p * p) ans += p*p*p + p*p + p + 1;
                    break;
                }
            }
        }
        return ans;
    }
    // Eratosthenes筛选法
    void eth() {
        f[0] = f[1] = 1; // 0,1不是素数
        primes[0] = 0; // 这个一定要写
        for(int i = 2; i < MAX; i ++) {
            if(f[i] == 0) {
                primes[++ primes[0]] = i; // primes[0]为计数
                for(long j = (long)i * i; j < MAX; j += i) { // 防止溢出
                    f[(int)j] = 1;
                }
            }
        }
    }
}