数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究将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。
60次浏览
