搬家网站建设案例说明,杭州百度推广网站建设,王野天,wordpress 红酒描述
求正整数N(N1)的质因数的个数。 相同的质因数需要重复计算。如1202*2*2*3*5#xff0c;共有5个质因数。
输入描述#xff1a;
可能有多组测试数据#xff0c;每组测试数据的输入是一个正整数N#xff0c;(1N10^9)。
输出描述#xff1a;
对于每组数…描述
求正整数N(N1)的质因数的个数。 相同的质因数需要重复计算。如1202*2*2*3*5共有5个质因数。
输入描述
可能有多组测试数据每组测试数据的输入是一个正整数N(1N10^9)。
输出描述
对于每组数据输出N的质因数的个数。
示例1
输入
120
输出
5
思路
只需要判断因数是否能够整除当前的数而无需判断因数本身是否为质数。质因数分解是将一个数分解为一系列质数的乘积而我们只需要关注能够整除的因数因为如果一个非质数能够整除当前的数那么它一定可以被分解为更小的因数的乘积。
例如考虑将120分解为质因数的过程
120 2 * 60
60 2 * 30
30 2 * 15
15 3 * 5
在这个过程中我们并没有判断2、3、5是否为质数只需要判断它们能否整除当前的数。因为即使它们不是质数它们也可以分解为更小的因数的乘积而最终会得到正确的质因数分解结果。
在质因数分解问题中我们只需要关注因数能否整除当前的数而无需判断因数本身是否为质数极大减少了代码的冗余运算但依然可以得到正确的结果。
源代码
#includeiostream
#includecmath
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;
}提交结果
编辑切换为居中
添加图片注释不超过 140 字可选
