在C++中实现分解质因数的功能可以通过以下步骤完成:
- 定义一个函数:用于接收一个整数,并返回其所有质因数。
- 处理2作为质因数的情况:因为2是最小的质数,首先检查给定的数是否能被2整除,如果可以,则2是一个质因数,记录下来,并将原数除以2,重复此过程直到不能被2整除为止。
- 处理大于2的质因数:从3开始,每次增加2(即只考虑奇数),检查当前数是否为质因数。如果是,则记录下来,并将原数除以此质因数,重复此过程直到不能被当前数整除为止。
- 处理特殊情况:如果最后剩下的数大于2,那么这个数本身也是一个质因数。
#include <iostream>
#include <vector>// 声明一个返回质因数的函数,先声明之后,就可以在主程序main()中使用了,如果不想用声明的方法,可以直接将函数写到main前面,否则无法在main中进行调用
std::vector<int> primeFactors(int n);int main() {int number;std::cout << "请输入一个正整数: ";std::cin >> number;std::vector<int> factors = primeFactors(number);std::cout << "质因数有: ";for(int i=0; i < factors.size();i++){if(i>0){std::cout << "*" << " ";}std::cout << factors[i]<< " ";}std::cout << std::endl;return 0;
}// 函数定义
std::vector<int> primeFactors(int n) {std::vector<int> factors;// 处理2作为质因数的情况while (n % 2 == 0) {factors.push_back(2);n /= 2;}// 处理大于2的质因数for (int i = 3; i * i <= n; i += 2) {while (n % i == 0) {factors.push_back(i);n /= i;}}// 如果n大于2,说明n本身是一个质数if (n > 2) {factors.push_back(n);}return factors;
}
我们看一下输出结果:
如果函数不用先声明的情况下,我们改一下程序:
#include <iostream>
#include <vector>int main() {int number;std::cout << "请输入一个正整数: ";std::cin >> number;std::vector<int> factors = primeFactors(number);std::cout << "质因数有: ";for(int i=0; i < factors.size();i++){if(i>0){std::cout << "*" << " ";}std::cout << factors[i]<< " ";}std::cout << std::endl;return 0;
}// 函数定义
std::vector<int> primeFactors(int n) {std::vector<int> factors;// 处理2作为质因数的情况while (n % 2 == 0) {factors.push_back(2);n /= 2;}// 处理大于2的质因数for (int i = 3; i * i <= n; i += 2) {while (n % i == 0) {factors.push_back(i);n /= i;}}// 如果n大于2,说明n本身是一个质数if (n > 2) {factors.push_back(n);}return factors;
}
执行时就会显示有错误,提示这个函数没有定义,
这个时候,我们就得把函数定义到main之前。
#include <iostream>
#include <vector>// 函数定义
std::vector<int> primeFactors(int n) {std::vector<int> factors;// 处理2作为质因数的情况while (n % 2 == 0) {factors.push_back(2);n /= 2;}// 处理大于2的质因数for (int i = 3; i * i <= n; i += 2) {while (n % i == 0) {factors.push_back(i);n /= i;}}// 如果n大于2,说明n本身是一个质数if (n > 2) {factors.push_back(n);}return factors;
}
int main() {int number;std::cout << "请输入一个正整数: ";std::cin >> number;std::vector<int> factors = primeFactors(number);std::cout << "质因数有: ";for(int i=0; i < factors.size();i++){if(i>0){std::cout << "*" << " ";}std::cout << factors[i]<< " ";}std::cout << std::endl;return 0;
}
又可以愉快的执行了