2521. Distinct Prime Factors of Product of Array

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics:
  • \(\color{blue}\textsf{Weekly Contest 323}\)

一、題目

Given an array of positive integers nums, return the number of distinct prime factors in the product of the elements of nums.
Note that:

  • A number greater than 1 is called prime if it is divisible by only 1 and itself.
  • An integer val1 is a factor of another integer val2 if val2 / val1 is an integer.

Example 1:

  • Input: nums = [2,4,3,7,10,6]
  • Output: 4
  • Explanation: The product of all the elements in nums is: 2 * 4 * 3 * 7 * 10 * 6 = 10080 = 2^5 * 3^2 * 5 * 7.
    There are 4 distinct prime factors so we return 4.

Example 2:

  • Input: nums = [2,4,8,16]
  • Output: 1
  • Explanation: The product of all the elements in nums is: 2 * 4 * 8 * 16 = 1024 = 210.
    There is 1 distinct prime factor so we return 1.

Constraints:

  • 1 <= nums.length <= 10^4
  • 2 <= nums[i] <= 1000

二、分析

  • 這一題是要求所有數字相乘的質因數分解，並求質因數的個數。
  • 我們並不需要真的將所有數字相乘，因為我們的目的是要將之作因數分解，而分解的過程中，可能會重複檢查到每個數字是否為質因數，為了避免重複檢查，可以將檢查過的數，用 dp 的方式記錄起來。或者是用 pre-built table 的方式，將是否為質數先計算出來。
  • 此題我用的方法是數論中，從 2 開始依序由小到大將倍數篩掉，此法有個很長的名子叫作 Sieve of Eratosthenes。 soe
  • 我們只需把 pre-built table 做到數列的最大值。
  • 在此我做了一個改版，我們將這個 table 記錄下最小的因數，方便做因數分解，這個 table 的特性是：
    • 當 table[i] == i 時，i 為質數。
    • 當 table[i] != i 時，table[i] 為 i 最小的質因數。
  • 以下是原始的 table：
    \(\begin{array}{|c|c|c|c|c|c|c|c|c|c|}\hline &2&3&4&5&6&7&8&9&10\\\hline 11&12&13&14&15&16&17&18&19&20\\\hline 21&22&23&24&25&26&27&28&29&30\\\hline 31&32&33&34&35&36&37&38&39&40\\\hline 41&42&43&44&45&46&47&48&49&50\\\hline \end{array}\)
  • 改良後的 table：
    \(\begin{array}{|c|c|c|c|c|c|c|c|c|c|}\hline &2&3&2&5&2&7&2&3&2\\\hline 11&2&13&2&3&2&17&2&19&2\\\hline 3&2&23&2&5&2&3&2&29&2\\\hline 31&2&3&2&5&2&37&2&3&2\\\hline 41&2&43&2&3&2&47&2&7&2\\\hline \end{array}\)
  • 有了上面這張改良後的表，因式分解就可以簡化成：
    • 當 table[num] == num 時，num 是質數
    • 否則 num = table[num] * num/table[num]，由於 table[num] 是最大因數，所以可以繼續分解直到變成質數。

三、解題

1. Sieve of Eratosthenes

  • Time complexity: \(O(n\sqrt{n}/\log n)\)
  • Space complexity: \(O(n/\log n)\)
vector<int> table;      // 在全域建一個 pre-built table
int distinctPrimeFactors(vector<int>& nums) {
    int upbound = *max_element(nums.begin(), nums.end());   // 求整個數列的最大值
    table.assign(upbound+1, 0);                             // table 只需求到最大值即可
    iota(table.begin(), table.end(), 0);                // 依序將 table[i] = i 填入 table

    for (int i = 2; i <= upbound; i++) {
        if (!table[i]) continue;                        // 當該數為合數時，跳過
        for (int j = 2*i; j <= upbound; j += i) {
            table[j] = i;                               // 將所有質數的倍數記錄下他
        }
    }
    
    unordered_set<int> set;                             
    for (const auto& num : nums) {
        find(num, set);                                 // 質因數分解
    }
    return set.size();                                  // 求質因數的個數
}
void find(int num, unordered_set<int>& set) {
    if (table[num] == num) {
        set.insert(num);                                // 當是質數就用 set 記錄下來
    } else {
        find(num/table[num], set);                      // 不是質數就繼續分解
        find(table[num], set);
    }
}

回目錄 Catalog