2017.11.29

质因数的个数

题目描述

求正整数N(N>1)的质因数的个数。 相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。

输入描述:

可能有多组测试数据，每组测试数据的输入是一个正整数N，(1<N<10^9)。

输出描述:

对于每组数据，输出N的质因数的个数。

示例1

输入

120

输出

5

#include <iostream>  
#include <cstdio>
#include <iomanip>  
#include <string>
#include <cmath>
//用setprecision(n)设置精度，其中n表示精确到小数点后n位  
//这题的关键：
//1、是sqrt,可以极大减少复杂度，若是到方根N仍大于1，则必还有且只还有1个质因数
//2、每次瞬间整除都可帮助减少遍历范围
using namespace std;

int main()
{
    int N;
    int count = 0;    
    while (cin >> N)
    {
        for (int i = 2; i <= sqrt(N); i++)
        {
            while (N%i == 0)
            {
                N = N / i;
                count++;
            }
            if (N <= 1) break;
        }
        if (N>1)
            count++;
        cout << count << endl;
        count = 0;
    }
    return 0;
}