思路:
只需要判断因数是否能够整除当前的数,而无需判断因数本身是否为质数。质因数分解是将一个数分解为一系列质数的乘积,而我们只需要关注能够整除的因数,因为如果一个非质数能够整除当前的数,那么它一定可以被分解为更小的因数的乘积。
例如,考虑将120分解为质因数的过程:
120= 2 * 60
60 = 2 * 30
30 = 2 * 15
15 = 3 * 5
在这个过程中,我们并没有判断2、3、5是否为质数,只需要判断它们能否整除当前的数。因为即使它们不是质数,它们也可以分解为更小的因数的乘积,而最终会得到正确的质因数分解结果。
在质因数分解问题中,我们只需要关注因数能否整除当前的数,而无需判断因数本身是否为质数,极大减少了代码的冗余运算,但依然可以得到正确的结果。
源代码:
#include<iostream> #include<cmath> using namespace std; //例题6.9 质因数的个数 int main() { int n; while (cin >> n) { int res = 0; for (int i = 2; i <= sqrt(n); i++) { while (n % i == 0) { res++; n /= i; } } if (n > 1) { res++; } cout << res << endl; } return 0; }