【poj - 2478 Farey Sequence （欧拉函数、数论）】-白红宇

【poj - 2478 Farey Sequence （欧拉函数、数论）】

阅读量：7071 次

发布时间：2019-06-28

本文共 2556 字，大约阅读时间需要 8 分钟。

Farey Sequence

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 9180		Accepted: 3501

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

⁶). 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

Sample Output

Source

,Author:Mathematica@ZSU

1 // Project name : 2478 ( Farey Sequence )  2 // File name    : main.cpp 3 // Author       : Izumu 4 // Date & Time  : Fri Jul 13 16:30:10 2012 5  6  7 #include 
      
        8 #include 
       
         9 #include 
        
         10 #include 
         
          11 #include 
          
           12 using namespace std;13 14 #define MAXN 100010015 16 typedef unsigned long long int longint;17 18 ///19 bool prime[MAXN];20 ///21 void CInitPrime()22 {23     for (int i = 0; i < MAXN; i++)24     {25         prime[i] = true;26     }27 28     int current_prime = 2;29     for (; current_prime * current_prime <= MAXN; current_prime++)30     {31         if (prime[current_prime] == true)32         {33             for (int i = current_prime * current_prime; i < MAXN; i = i + current_prime)34             {35                 prime[i] = false;36             }37         }38     }39 }40 ///41 longint phi[MAXN];42 ///43 void CInitPhi()44 {45     for (int i = 1; i < MAXN; i++)46     {47         phi[i] = i;48     }49 50     for (int i = 2; i < MAXN; i++)51     {52         if (prime[i])53         {54             for (int j = i; j < MAXN; j += i)55             {56                 phi[j] = phi[j] / i * (i - 1);57             }58         }59     }60 }61 ///62 int main()63 {64     CInitPrime();65     CInitPhi();66     int index;67     while (cin >> index && index)68     {69         longint sum = 0;70         for (int i = 2; i <= index; i++)71         {72             sum += phi[i];73         }74         cout << sum << endl;75     }76     return 0;77 }78 79 // end 80 // ism