Very Simple Counting
--------------------------------------------------------------------------------
Time Limit: 1 Second Memory Limit: 32768 KB
--------------------------------------------------------------------------------
Let f(n) be the number of factors of integer n.
Your task is to count the number of i(1 <= i < n) that makes f(i) = f(n).
Input
One n per line (1 < n <= 1000000).
There are 10000 lines at most.
Output
For each n, output counting result in one line.
Sample Input
4
5
Sample Output
0
2
Hint
f(1) = 1, f(2) = f(3) = f(5) = 2, f(4) = 3.
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int sum[1000010],ans[1000010];
int flag[1000010],pl;//flag[i]==0表示是素数
void _prime()
{
for(int i=2;i<500005;i++) flag[i<<1]=2;//flag[j]=i表示j由i筛选得来
for(int i=3;i<=1000;i+=2)
{
if(flag[i]==0)
{
for(int j=i*i;j<=1000000; flag[j]=i,j+=2*i);
}
}
}
void _getfac()//分解质因子,
{
ans[1]=0;sum[1]=1;
for(int i=2;i<=1000000;i++)
{
if(flag[i]==0)
{
sum[2]++;
ans[i]=sum[2]-1;
continue;
}
int cnt=1;
int n=i;
while(n>1)
{
int _c=0;
for(int k=flag[n]?flag[n]:n;n%k==0;_c++,n/=k);//此处极是巧妙 需要学习
cnt*=(_c+1);
}
sum[cnt]++;
ans[i]=sum[cnt]-1;//判断也很巧妙 需要学习
}
}
int main()
{
_prime();
_getfac();
int n;
while(scanf("%d",&n)==1)
{
printf("%d/n",ans[n]);
}
return 0;
}