四因数

1390. 四因数

给你一个整数数组 nums，请你返回该数组中恰有四个因数的这些整数的各因数之和。如果数组中不存在满足题意的整数，则返回 0 。

示例 1：

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

示例 2:

输入: nums = [21,21]
输出: 64

示例 3:

输入: nums = [1,2,3,4,5]
输出: 0

提示：

1 <= nums.length <= 10⁴
1 <= nums[i] <= 10⁵

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int sumFourDivisors(vector<int>& nums) { } };

golang 解法, 执行用时: 24 ms, 内存消耗: 6.2 MB, 提交时间: 2023-09-07 15:01:06

/**
 * 当一个数有四因数时，其中1和它本身肯定是两个因数。
 * 那么另外两个必须都是素数，或者一个是素数另一个是该素数的平方，
 * 否则一定可以通过继续拆解另一个数得到更多因数。
 * 得到该结论后我们可以用素数筛先取到5e4以内的素数，
 * 然后对2到sqrt(i)内的素数尝试能否整除该数进行判断，
 * 符合以上结论时就将所有因数加入最后答案。
 */
func sumFourDivisors(nums []int) int {
	su := make([]bool, 5e4+5)
	for i := 2; i <= 5e4; i++ {
		if !su[i] {
			for j := i + i; j <= 5e4; j += i {
				su[j] = true
			}
		}
	}
	s := []int{}
	for i := 2; i <= 5e4; i++ {
		if !su[i] {
			s = append(s, i)
		}
	}
	judge := func(num int) int {
		for i := range s {
			if s[i]*s[i] >= num {
				return 0
			}
			if num%s[i] == 0 && (!su[num/s[i]] || num/s[i] == s[i]*s[i]) {
				return 1 + num + s[i] + num/s[i]
			}
		}
		return 0
	}
	res := 0
	for i := range nums {
		res += judge(nums[i])
	}
	return res
}

java 解法, 执行用时: 47 ms, 内存消耗: 47.3 MB, 提交时间: 2023-09-07 14:59:09

class Solution {
    public int sumFourDivisors(int[] nums) {
        // C 是数组 nums 元素的上限，C3 是 C 的立方根
        int C = 100000, C3 = 46;
        
        boolean[] isPrime = new boolean[C + 1];
        Arrays.fill(isPrime, true);
        List<Integer> primes = new ArrayList<Integer>();

        // 埃拉托斯特尼筛法
        for (int i = 2; i <= C; ++i) {
            if (isPrime[i]) {
                primes.add(i);
            }
            for (int j = i + i; j <= C; j += i) {
                isPrime[j] = false;
            }
        }

        // 欧拉筛法
        /*
        for (int i = 2; i <= C; ++i) {
            if (isPrime[i]) {
                primes.add(i);
            }
            for (int prime : primes) {
                if (i * prime > C) {
                    break;
                }
                isPrime[i * prime] = false;
                if (i % prime == 0) {
                    break;
                }
            }
        }
        */
        
        // 通过质数表构造出所有的四因数
        Map<Integer, Integer> factor4 = new HashMap<Integer, Integer>();
        for (int prime : primes) {
            if (prime <= C3) {
                factor4.put(prime * prime * prime, 1 + prime + prime * prime + prime * prime * prime);
            }
        }
        for (int i = 0; i < primes.size(); ++i) {
            for (int j = i + 1; j < primes.size(); ++j) {
                if (primes.get(i) <= C / primes.get(j)) {
                    factor4.put(primes.get(i) * primes.get(j), 1 + primes.get(i) + primes.get(j) + primes.get(i) * primes.get(j));
                } else {
                    break;
                }
            }
        }

        int ans = 0;
        for (int num : nums) {
            if (factor4.containsKey(num)) {
                ans += factor4.get(num);
            }
        }
        return ans;
    }
}

python3 解法, 执行用时: 868 ms, 内存消耗: 22.4 MB, 提交时间: 2023-09-07 14:58:29

# 埃拉托斯特尼筛法 / 欧拉筛法 , 预处理
class Solution:
    def sumFourDivisors(self, nums: List[int]) -> int:
        # C 是数组 nums 元素的上限，C3 是 C 的立方根
        C, C3 = 100000, 46

        isprime = [True] * (C + 1)
        primes = list()

        # 埃拉托斯特尼筛法，筛选出素数
        for i in range(2, C + 1):
            if isprime[i]:
                primes.append(i)
            for j in range(i + i, C + 1, i):
                isprime[j] = False
        
        # 欧拉筛法
        """
        for i in range(2, C + 1):
            if isprime[i]:
                primes.append(i)
            for prime in primes:
                if i * prime > C:
                    break
                isprime[i * prime] = False
                if i % prime == 0:
                    break
        """
        
        # 通过质数表构造出所有的四因数
        factor4 = dict()
        for prime in primes:
            if prime <= C3:
                factor4[prime**3] = 1 + prime + prime**2 + prime**3
        for i in range(len(primes)):
            for j in range(i + 1, len(primes)):
                if primes[i] * primes[j] <= C:
                    factor4[primes[i] * primes[j]] = 1 + primes[i] + primes[j] + primes[i] * primes[j]
                else:
                    break
        
        ans = 0
        for num in nums:
            if num in factor4:
                ans += factor4[num]
        return ans

java 解法, 执行用时: 32 ms, 内存消耗: 42.1 MB, 提交时间: 2023-09-07 14:56:13

class Solution {
    public int sumFourDivisors(int[] nums) {
        int ans = 0;
        for (int num : nums) {
            // factor_cnt: 因数的个数
            // factor_sum: 因数的和
            int factor_cnt = 0, factor_sum = 0;
            for (int i = 1; i * i <= num; ++i) {
                if (num % i == 0) {
                    ++factor_cnt;
                    factor_sum += i;
                    if (i * i != num) {   // 判断 i 和 num/i 是否相等，若不相等才能将 num/i 看成新的因数
                        ++factor_cnt;
                        factor_sum += num / i;
                    }
                }
            }
            if (factor_cnt == 4) {
                ans += factor_sum;
            }
        }
        return ans;
    }
}

python3 解法, 执行用时: 1152 ms, 内存消耗: 17 MB, 提交时间: 2023-09-07 14:55:56

class Solution:
    def sumFourDivisors(self, nums: List[int]) -> int:
        ans = 0
        for num in nums:
            # factor_cnt: 因数的个数
            # factor_sum: 因数的和
            factor_cnt = factor_sum = 0
            i = 1
            while i * i <= num:
                if num % i == 0:
                    factor_cnt += 1
                    factor_sum += i
                    if i * i != num:   # 判断 i 和 num/i 是否相等，若不相等才能将 num/i 看成新的因数
                        factor_cnt += 1
                        factor_sum += num // i
                i += 1
            if factor_cnt == 4:
                ans += factor_sum
        return ans

上一题

下一题

详情