#include <iostream>
#include <vector>
using namespace std;
// 对正整数进行唯一分解
vector<pair<int, int>> primeFactorization(int n) {
	vector<pair<int, int>> factors;
	for (int i = 2; i * i <= n; ++i) {
		int exponent = 0;//幂数数
		while (n % i == 0) {
			n /= i;
			++exponent;
		}
		if (exponent > 0) {
			//factors.emplace_back(i, exponent);//隐式封装
			factors.push_back(make_pair(i, exponent));//显式封装
		}
	}
	if (n > 1) {
		factors.emplace_back(n, 1);
	}
	return factors;
}
int main() {
	int num;
	cout << "请输入一个正整数: ";
	cin >> num;
	
	auto result = primeFactorization(num);
	//auto vector类型
	cout << num << " 的唯一分解形式为: ";
	//result.size()获取vector的长度
	//size_t 短整数 size_t含义专门存储数组等STL容器的长度
	for (size_t i = 0; i < result.size(); ++i) {
		cout << result[i].first;//20 = 2^2 * 5
		if (result[i].second > 1) {
			cout << "^" << result[i].second;
		}
		if (i < result.size() - 1) {
			cout << " * ";
		}
	}
	cout << endl;
	return 0;
}    

2032：【例4.18】分解质因数

时间限制: 1000 ms 内存限制: 65536 KB 提交数:56003 通过数: 35791

【题目描述】 把一个合数分解成若干个质因数乘积的形式(即求质因数的过程)叫做分解质因数。分解质因数(也称分解素因数)只针对合数。

输入一个正整数n，将n分解成质因数乘积的形式。

【输入】 一个正整数n。

【输出】 分解成质因数乘积的形式。质因数必须由小到大，见样例。

【输入样例】

36

【输出样例】

36=2*2*3*3

【提示】 【数据范围】

对于所有数据，2≤n≤20000。

#include<iostream>
using namespace std;
int main() {
	int n;
	cin >> n;
	int i = 2;
	cout<<n<<"=";
	bool flag = true;//true表示是第一个数
	while(n!=1){
		if(n%i==0){//5它能被5
			while(n % i == 0){//5能被5整除
				n/=i;
				if(flag == true){
					cout<<i;
					flag = false;
				}else{
					cout<<"*"<<i;
				}
			}
		}
		i+=1;//6
	}
	return 0;
}

用C++实现一个程序，对给定的正整数进行唯一分解

#include <iostream>
#include <vector>
using namespace std;

// 对正整数进行唯一分解
vector<pair<int, int>> primeFactorization(int n) {
    vector<pair<int, int>> factors;
    for (int i = 2; i * i <= n; ++i) {
        int exponent = 0;
        while (n % i == 0) {
            n /= i;
            ++exponent;
        }
        if (exponent > 0) {
            factors.emplace_back(i, exponent);
        }
    }
    if (n > 1) {
        factors.emplace_back(n, 1);
    }
    return factors;
}

int main() {
    int num;
    cout << "请输入一个正整数: ";
    cin >> num;

    auto result = primeFactorization(num);

    cout << num << " 的唯一分解形式为: ";
    for (size_t i = 0; i < result.size(); ++i) {
        cout << result[i].first;
        if (result[i].second > 1) {
            cout << "^" << result[i].second;
        }
        if (i < result.size() - 1) {
            cout << " * ";
        }
    }
    cout << endl;

    return 0;
}    

你已经给出了部分代码，下面我会基于你给出的头文件和命名空间，补全代码实现对给定正整数进行唯一分解的功能。

代码解释

1. primeFactorization 函数：
   • 该函数接收一个正整数 n 作为参数，返回一个 vector<pair<int, int>> 类型的结果，其中每个 pair 存储一个质因数及其对应的指数。
   • 从最小的质数 2 开始，通过循环 for (int i = 2; i * i <= n; ++i) 来尝试将 n 分解。对于每个可能的质因数 i，使用 while 循环计算其在 n 中的指数 exponent。
   • 如果 exponent 大于 0，说明 i 是 n 的一个质因数，将其和对应的指数作为一个 pair 存入 factors 中。
   • 当循环结束后，如果 n 仍然大于 1，说明 n 本身是一个质数，将其作为一个质因数存入 factors 中，指数为 1。
2. main 函数：
   • 提示用户输入一个正整数，并将其存储在变量 num 中。
   • 调用 primeFactorization 函数对 num 进行分解，将结果存储在 result 中。
   • 遍历 result，按照质因数和指数的格式输出分解结果，不同质因数之间用 * 连接。

复杂度分析