C++ 将N转换为M所需的每步添加到N中的质因数计数

在这个问题中，我们将通过将N的一个质因数添加到自身并在每次操作中更新它来将数字N转换为M。

我们将使用广度优先搜索算法来解决这个问题。我们将找到每个已更新的N的质因数，并在将其添加到N的质因数后将其插入队列中。此外，我们将定义函数来查找特定数字的最小质因数。

问题说明 - 给定N和M的整数值。我们需要计算将N转换为M所需的最少操作次数。在每个操作中，我们需要取得N的更新值的一个质因数，并将其添加到N中。如果能够将N转换为M，则打印最小操作计数。否则，打印-1。

示例

输入

N = 8, M = 12;

输出

2

解释

• 在第一次操作中，取8的质因数’2’并将其加到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。

• 在第一步中，我们将用距离为0将3添加到队列中。

• 然后，我们将得到3的质因数，即{3}。

• 在下一步中，我们将用距离为1将6（3 + 3）添加到队列中。

• 然后，我们将找到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

时间复杂度 – 将N转换为M的时间复杂度为O(M)。

空间复杂度 – 将数对存储到队列中的空间复杂度为O(M)。

我们通过一个问题学习了三个不同的子问题。第一个子问题是使用筛选算法找到每个数字的最小质数。第二个子问题是找到给定数字的所有质因数，第三个子问题是通过将N的任何质因数加到自身来将N转换为M。