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<stdio.h>
int prime[1000005]={0};
int sum[1000005]={0};
int p[1000005]={0};
void prim()
{
prime[1]=prime[0]=1;
for(int i=1;i<=500000;++i) prime[i<<1]=2;
for(int i=3;i<=1000;++i)
if(prime[i]==0)
{
prime[i]=i;
int k=i*i;
while(k<1000000)
{
if(prime[k]==0) prime[k]=i;
k+=i;
}
}
for(int i=2;i<=1000000;++i)
if(prime[i]==0) prime[i]=i;
}
int main()
{
prim();
sum[1]++;p[1]=0;
for(int i=2;i<=1000000;i++)
if(prime[i]==i)
{
sum[2]++;
p[i]=sum[2]-1;
}
else
{
int ans=1;
int t=i;
while(t>1)
{
int k=prime[t];
int count=1;
while(t%k==0)
{
t=t/k;
count++;
}
ans=ans*count;
}
sum[ans]++;
p[i]=sum[ans]-1;;
}
int n;
while(scanf("%d",&n)!=EOF)
{
printf("%d/n",p[n]);
}
return 0;
}