Description
The Farey Sequence Fn for any integer n with n >= 2 is the set of irreducible rational numbers a/b with 0 < a < b <= n and gcd(a,b) = 1 arranged in increasing order. The first few are 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
There are several test cases. Each test case has only one line, which contains a positive integer n (2 <= n <= 10 6 ). There are no blank lines between cases. A line with a single 0 terminates the input.Output
For each test case, you should output one line, which contains N(n) ---- the number of terms in the Farey sequence Fn.Sample Input
2 3 4 5 0Sample Output
1 3 5 9Source
POJ Contest ,Author:Mathematica@ZSU 法拉雷数列：通过观察可以看出其实是NUM（Fn）=（phi（1）+phi（2）+phi（3）+……+phi（n））； 也就是连续区间上的欧拉函数值求和； 对于这个问题欧拉函数的值总是要重复用到的所以我们希望一次求出1……n的phi（i）；那么怎么样才能高效的求出呢？ 通过欧拉函数的性质： 所以在进行线性时间筛法时我们就可以把欧拉函数值求出来； 通过一次求出前缀和便解决了问题； 代码如下： #include <iostream> #define maxlen 1000050 using namespace std; bool is_prime[maxlen]={0}; int prime[maxlen]; int phi[maxlen]; long long sum[maxlen]; void linear_prime() { int i=2; int j=0; int k; phi[1]=1; for(i=2;i<=maxlen;i++) { if(!is_prime[i]) { prime[j++]=i; phi[i]=i-1; //if(i==2) //cout<<prime[j-1]<<endl; } //cout<<j<<endl; for(k=0;k<j;k++) { if(i*prime[k]>maxlen) break; is_prime[i*prime[k]]=1; //cout<<i*prime[k]<<endl; if(i%prime[k]==0) { phi[i*prime[k]]=phi[i]*prime[k]; break; } else { phi[i*prime[k]]=phi[i]*(prime[k]-1); } } } } int main() { int i,j; //system("pause"); linear_prime(); for(i=2;i<=maxlen;i++) sum[i]=sum[i-1]+phi[i]; //cout<<prime[0]<<endl; //system("pause"); //system("pause"); int k; while(cin>>k&&k) cout<<sum[k]<<endl; return 0; }