| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 6416 | Accepted: 2316 |
Description
F2 = {1/2}
F3 = {1/3, 1/2, 2/3}
F4 = {1/4, 1/3, 1/2, 2/3, 3/4}
F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}
You task is to calculate the number of terms in the Farey sequence Fn.
Input
Output
Sample Input
2 3 4 5 0
Sample Output
1 3 5 9
Source
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int oula[1000010];
long long sum[1000010];
int is[1000010],prime[1000010],pl;
void getprime()
{
for(int i=2;i<1000010;i++)
{
if(is[i]==0) prime[pl++]=i;//0表示素数
for(int j=0;j<pl&&i*prime[j]<1000010;j++)
{
is[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
int main()
{
getprime();
//欧拉函数递推性质：如果素数p|x：如果p*p|x,则oula[x]=oula[x/p]*p;否则oula[x]=oula[x/p]*(p-1)
for(int i=2;i<=1000000;i++)//此题中不用考虑1
{
if(is[i]==0) oula[i]=i-1;
else
{
double k=sqrt(0.5+i);
for(int j=0;j<pl&&prime[j]<=k;j++)
{
if(i%prime[j]==0)
{
if(i%(prime[j]*prime[j])==0) oula[i]=oula[i/prime[j]]*prime[j];
else oula[i]=oula[i/prime[j]]*(prime[j]-1);
break;
}
}
}
sum[i]=oula[i]+sum[i-1];
}
int n;
while(scanf("%d",&n)==1&&n)
{
cout<<sum[n]<<endl;
}
return 0;
}