概述
LeetCode 1183题要求我们找到数组中数字的“质因子”之和。一个数字的质因子是指能够整除该数字的质数。例如，数字60的质因子为2、3和5，因为2、3和5都是质数且能整除60。
题目描述
给定一个正整数数组
nums
，找到每个数字的质因子之和，然后返回这些和的总和。
解题思路
为了解决这个问题，我们可以采用以下步骤：
质数生成
：首先，我们需要一个生成质数的方法。可以使用埃拉托斯特尼筛法（Sieve of Eratosthenes）来生成一个质数列表。
计算质因子和
：对于数组中的每个数字，我们可以使用前面生成的质数列表来计算其质因子和。
求和
：最后，我们将所有数字的质因子和相加，得到最终结果。
Java代码实现
import java.util.ArrayList;
import java.util.List;
public class Solution {
public int sumOfQuality(int[] nums) {
// 步骤1: 生成质数列表
List
// 步骤2: 计算每个数字的质因子和
int sum = 0;
for (int num : nums) {
sum += sumOfPrimeFactors(num, primes);
}
// 步骤3: 返回总和
return sum;
}
private List
boolean[] isPrime = new boolean[max + 1];
for (int i = 2; i <= max; i++) {
isPrime[i] = true;
}
for (int factor = 2; factor * factor <= max; factor++) {
if (isPrime[factor]) {
for (int j = factor * factor; j <= max; j += factor) {
isPrime[j] = false;
}
}
}
List
for (int i = 2; i <= max; i++) {
if (isPrime[i]) {
primes.add(i);
}
}
return primes;
}
private int sumOfPrimeFactors(int num, List
int sum = 0;
for (int prime : primes) {
while (num % prime == 0) {
sum += prime;
num /= prime;
}
if (num == 1) {
break;
}
}
return sum;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {10, 15, 3, 5};
System.out.println(sol.sumOfQuality(nums)); // 输出应为 32
}
}
性能分析
质数生成
：使用埃拉托斯特尼筛法，时间复杂度为O(n log log n)。
计算质因子和
：对于每个数字，我们需要遍历质数列表，时间复杂度为O(sqrt(n))，其中n是数字本身。
求和
：对数组中每个数字进行质因子和的计算，时间复杂度为O(m * sqrt(n))，其中m是数组长度。
总的来说，该解决方案的时间复杂度主要取决于数组中数字的大小和数量。