【C++ 程序】质因数分解

it2025-11-06 13

程序

#include <iostream> #include <vector> #include <cmath> using namespace std; vector<unsigned> prime; // a vector that contains prime numbers void prime_def(int n) // define the vector { for (int ii = 2; ii <= n; ii++) { int index = 1; for (int j = 2; j <= sqrt(ii); j++) if (ii % j == 0) index = 0; if (index == 1) prime.push_back(ii); } } void fact(int n) { if (n == 1) cout << 1 << endl; else { int alr = 1; if (n == *(--prime.cend())) // If n is a prime number, just print itself. // Otherwise in the for loop, // subscript will be out of range // because when doing i++, // it will go to one beyond the end. cout << n; else { for (size_t i = 0; prime[i] <= n / alr; i++) { int state = 0; while (state == 0) { if (n / alr % prime[i] == 0) { cout << ((alr == 1) ? "" : " * ") << prime[i]; alr *= prime[i]; } else state = 1; } } } cout << endl; } } int main() { int n; cin >> n; cout << n << " = "; prime_def(abs(n)); if (n < 0) { cout << "- "; n = -n; // change into the positive } fact(n); return 0; }

输出示例

分析

如果是质数的时候很容易出错。因为会走到最后一个vector空间的外面，这样就炸了（subscript out of range）。解决方案：如果就是质数vector中的最后一个，即就是质数，直接输出。（26行有的判断）

【C++ 程序】 质因数分解

程序

输出示例

分析

See also

【C++ 程序】质因数分解