求解因子个数思路分析

笔者在拿到这道题的时候，一开始思路是从从2开始，如果n能整除i,那么n/=i,一直到n不能整除i，因子数+1，再开始判断n能否整除i+1,一直这样做退出条件是n==1.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        int sum=0;
        for(int i=2;i!=n;i++)
        {
            int d=0;//用于判断i是否可以作为一个因子
            whlie(n%i==0)
            {
                n/=i;
                d=1;//i可以作为因子，d变1 
            } 
            if(d) sum++; 
        }
        cout<<sum<<endl;
    }
 } 

上面的代码其实可以解决这个问题，但是会超时，问题就在于当n的某个因子为极大的质数时候或者n本身就是极大的质数时候，i便要从2一直一个试到那个极大的质数，这样便会耗费大量时间。
这时我们便可以借鉴我们之前用过判断一个数是否为质数的办法，比如要判断n是否为质数，我们只要看从
2<=i<sqrt(n)这个范围有没有n的因子便可，这样便缩小了搜寻范围。
所以我们改进版的代码如下，循环终结的条件变成i<sqrt(n),这样的话，在n逐渐变小的同时，搜索范围也随着变小，倘如退出循环后，n!=1，这说明最后的n是一个质数，我们只需要在因子数上再+1便可。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        int sum=0;
        for(int i=2;i<sqrt(n);i++)
        {
            int d=0;
            while(n%i==0)
            {
                d=1;
                n=n/i; 
            }

            if(d) sum++;
            if(n==1) break;
        }
        if(n!=1) sum++;
        cout<<sum<<endl;
    }
 }