学步园

做的第一个素数筛题，两天终于过了.........

思路：开一个大数组保存每个数的最小素因子，因子数f(N)就是所有素因子的次数加1相乘

N=p1^x1 + p2^x2 + .... + pk^xk;

则  f(N)=(x1+1)*(x2+1)*.....*(xk+1);

测试数据很多，用cin，cout会超时，所以用scanf，printf输出.........

#include <cstdio>
using namespace std;
int n,mins[1000001];
void findmins(){
    mins[0]=1;
    mins[1]=1;
    for(int i=2;i<=1000000;i+=2)
        mins[i]=2;
    for(int i=3;i<1001;i++)
    {
        if(mins[i]==0)
        {
            mins[i]=i;
            for(int j=i*i;j<=1000000;j+=i)
                if(mins[j]==0)
                    mins[j]=i;
        }
    }
    for(int i=2;i<=1000000;i++)
        if(mins[i]==0)
            mins[i]=i;
}
int main()
{
    findmins();
    while(scanf("%d",&n)!=EOF)
    {
        int ans=1;
        int t=n;
        while(t>1)
        {
            int count=1;
            int k=mins[t];
            while(t%k==0)
            {
                t/=k;
                count++;
            }
            ans*=count;
        }
        printf("%d %d\n",ans-1,n/mins[n]);
    }
    return 0;
}