质因数个数

思路：这题思路比较简单，即用待分解的数n逐步除以质因数，每除以一次就把个数num++，最后直到n=1或者找不到除n本身外的质因数（这里需要注意，因为这种情况需要把num+1，考虑n=37，它只有自己一个质因数，但是我们因数取得范围只有2~sqrt(37)）。为了学习判断一个数是不是指数6，我还上网学习了判断质数的方法（其实这道题并不用判断除数是不是质因数，因为随着除数是每一轮+1循环判断是不是质因数的，若后面的除数是合数，那么这个除数肯定可以分解成比它更小的质数相乘，所以除数是不可能变到一个合数的）

#include<iostream>
#include<cmath>
using namespace std;

bool isPrime(int a)
{
    if (a <= 3)
        return true;
    if (a % 6 != 1 && a % 6 != 5)//a可能为 6k-1,6k,6k+1,6k+2,6k+3,6k+4，其中6k,6k+2,6k+3,6k+4均不可能是素数
        return false;
    int sq = sqrt(a);
    for (int i = 5; i <= sq; i+=6) {//到了这里只有漏网之鱼n=6k-1或6k+1了，这两个明显是奇数。
        if (a%i == 0 || a % (i + 2) == 0)//若n%(6i+2),(6i),(6i+4)==0,那么n明显是偶数，不符合漏网之鱼的特征；若n%(6i+3)==0，那么n%3==0，
            return false;//但是6k%3==0,6k-1和6k+1在6k两边，明显n%3!=0，又不符合漏网之鱼得特征。所以漏网之鱼的因子只有可能是(6i-1)或(6i-1)
    }
    return true;
}

int main()
{
    int N, num = 0;
    while (cin >> N) {
        int s = sqrt(N);
        for (int i = 2; i <= s && N != 1;) {
            if (!isPrime(i)) {
                ++i;
                continue;
            }
            if (N%i == 0) {
                ++num;
                N /= i;
                continue;
            }
            else
                ++i;
        }
        if(N!=1)
            cout << num+1 << endl;
        else
            cout<<num<<endl;
        num = 0;
    }
}