將N轉換為M的每個步驟中要新增的N的質因數個數

---

在這個問題中，我們將透過在每次操作中將N的一個質因數加到自身並更新它來將數字N轉換為M。

我們將使用廣度優先搜尋演算法來解決這個問題。我們將找到每個更新後的N的質因數，並在將其新增到N的質因數後將其插入佇列。此外，我們還將定義函式來查詢特定數字的最小質因數。

問題陳述 - 我們給出了N和M整數的值。我們需要計算將N轉換為M所需的最小操作次數。在每次操作中，我們需要取更新後的N值的其中一個質因數並將其加到N上。如果可以將N轉換為M，則列印最小操作次數。否則，列印-1。

示例

輸入

N = 8, M = 12;

輸出

2

解釋 

• 在第一次操作中，取“2”（8的質因數）並將其加到8上。因此，N變為10。

• 在接下來的操作中，再次將2加到10上。

輸入

N = 7, M = 13;

輸出

-1

解釋 - 7和13都是質數。因此，無法將N轉換為M。

輸入

N = 7, M = 14;

輸出

1

解釋 - 7是7的質因數。因此，當我們將7加到7上時，我們可以在一次操作中得到14。

方法

在這種方法中，我們將使用篩法演算法計算2到100009範圍內每個數字的最小質因數。

之後，我們將使用佇列資料結構來維護新增質因數後更新的N值，並將其與達到更新值的所需操作次數對映。

例如，我們希望將3變成9。

• 第一步，我們將3與距離0一起新增到佇列中。

• 之後，我們將得到3的質因數，即{3}。

• 下一步，我們將6（3 + 3）與距離1一起新增到佇列中。

• 之後，我們將找到6的質因數，即{2, 3}。

• 因此，我們將{8, 2}（6+2, 1+1）和{9, 2}（6 + 3, 1 + 1）對插入佇列。這裡，對的第一個元素是更新後的值，對的第二個元素是遞增1後的距離。

• 之後，我們從佇列中獲取{8, 2}對。8的質因數是{2}。因此，我們將{10, 3}插入佇列。

• 接下來，我們從佇列中獲取{9, 2}。這裡，9等於M。因此，我們列印2作為答案。

演算法

步驟1 - 定義大小為100009的prime[]陣列以儲存每個數字的最小質因數。

步驟2 - 之後，定義getPrimeNumbers()函式來查詢每個數字的最小質因數。

步驟2.1 - 將所有prime[]陣列元素初始化為-1。

步驟2.2 - 從2開始遍歷陣列，並遍歷直到p*p小於100009。此外，使用巢狀迴圈從第p個索引開始更新每個第p個索引。

步驟2.3 - 在巢狀迴圈中，如果prime[q]為-1，則將其更新為p值。

步驟3 - 定義getPrimeFactors()函式來查詢特定值的全部質因數。

步驟3.1 - 定義'p_factors'集合以儲存質因數。

步驟3.2 - 遍歷給定數字，直到其值小於1。

步驟3.3 - 在迴圈中，將prime[num]插入p_factors集合中，它是數字的最小質因數。

步驟3.4 - 將數字除以最小質因數。

步驟3.5 - 當迴圈完成所有迭代時，返回p_factors集合。

步驟4 - 在findMinimumSteps()函式中，定義佇列以儲存更新後的N值對和所需操作次數。並將{n, 0}對插入佇列。

步驟5 - 迭代直到佇列變空。

步驟5.1 - 從佇列中彈出第一對。此外，將對的第一個元素儲存在'temp'變數中，並將對的第二個元素儲存在'dist'變數中。

步驟5.2 - 如果temp等於m，則返回'dist'值。

步驟5.3 - 如果'temp'大於m，則中斷迴圈。

步驟5.4 - 執行getPrimeFactors()函式以獲取'temp'的質因數，並將它們儲存到'p_factors'集合中。

步驟5.5 - 現在，遍歷p_factors集合的每個元素。

步驟5.5.1 - 將{temp + p, dist + 1}對插入佇列以供每個質因數使用。

步驟6 - 在函式末尾返回-1。

示例

#include <bits/stdc++.h>
using namespace std;
// To store all prime numbers
int prime[100009];
// To find prime numbers
void getPrimeNumbers() {
    // Initializing with -1
    memset(prime, -1, 100005);
    // Pre-computing smallest prime factor
    for (int p = 2; p * p <= 100005; p++) {
        for (int q = p; q <= 100005; q += p) {
            if (prime[q] == -1) {
                prime[q] = p;
            }
        }
    }
}
// Finding unique prime factors of n
set<int> getPrimeFactors(int num) {
    set<int> p_factors;
    // Store distinct prime factors
    while (num > 1) {
        p_factors.insert(prime[num]);
        num /= prime[num];
    }
    return p_factors;
}
int findMinimumSteps(int n, int m) {
    // To store distance from the start node
    queue<pair<int, int>> que;
    // BFS algorithm
    que.push({n, 0});
    while (!que.empty()) {
        // Get the first node from the queue
        int temp = que.front().first;
        int dist = que.front().second;
        que.pop();
            // When the temp is equal to m, we found steps
            if (temp == m) {
                return dist;
            }
            // When it is not possible to convert N to M
            else if (temp > m) {
                break;
            }
        // Finding prime factors
        set<int> p_factors = getPrimeFactors(temp);
        // Traverse prime factors
        for (auto p : p_factors) {
                // Insert pair to queue
                que.push({temp + p, dist + 1});
        }
    }
    // If we can't convert N to M
    return -1;
}
int main() {
    int N = 8, M = 12;
    getPrimeNumbers();
    int res = findMinimumSteps(N, M);
    if (res == -1) {
        cout << "It is not possible to convert " << N << " to " << M;
    } else {
        cout << "The minimum steps required to convert" << N << " to " << M << " is " << res;
    }
}

輸出

The minimum steps required to convert8 to 12 is 2

時間複雜度 - O(M) 將N轉換為M。

空間複雜度 -O(M) 將對儲存到佇列中。

我們使用單個問題學習了三個不同的子問題。第一個是使用篩法演算法查詢每個數字的最小質數。第二個是查詢給定數字的所有質因數，第三個是透過將N的任何質因數加到自身來將N轉換為M。