leetcode 1390

1390: 四因数

思路一：枚举

我们可以遍历数组 nums 中的每个元素，依次判断这些元素是否恰好有四个因数。对于任一元素 x，我们可以用类似质数判定的方法得到它的因数个数，其本质为：如果整数 x 有因数 y，那么也必有因数 x/y，并且 y 和 x/y 中至少有一个不大于 sqrt(x)。这样我们只需要在 [1, sqrt(x)] 的区间内枚举可能为整数 x 的因数 y，并通过 x/y 得到整数 x 的其它因数。

如果 x 恰好有四个因数，我们就将其因数之和累加到答案中。

class Solution { public: int sumFourDivisors(vector<int>& nums) { int ans=0; for(int x:nums){ int cnt=0,total=0; for(int i=1;i<=sqrt(x);i++){ int j=x/i; if(j*i==x){ if(j==i){ cnt++; total+=i; } else{ cnt+=2; total+=i+j; } } } if(cnt==4) ans+=total; } return ans; } };

进阶：埃拉托斯特尼筛法（埃氏筛）

class Solution { public: int sumFourDivisors(vector<int>& nums) { // C 是数组 nums 元素的上限，C3 是 C 的立方根 int C = 100000, C3 = 46; vector<int> isprime(C + 1, 1); vector<int> primes; // 埃拉托斯特尼筛法 for (int i = 2; i <= C; ++i) { if (isprime[i]) { primes.push_back(i); } for (int j = i + i; j <= C; j += i) { isprime[j] = 0; } } // 通过质数表构造出所有的四因数 unordered_map<int, int> factor4; for (int prime: primes) { if (prime <= C3) { factor4[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[i] <= C / primes[j]) { factor4[primes[i] * primes[j]] = 1 + primes[i] + primes[j] + primes[i] * primes[j]; } else { break; } } } int ans = 0; for (int num: nums) { if (factor4.count(num)) { ans += factor4[num]; } } return ans; } };