POJ2407(欧拉函数)

Relatives

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 13598		Accepted: 6771

Description

Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz.

Input

There are several test cases. For each test case, standard input contains a line with n <= 1,000,000,000. A line containing 0 follows the last case.

Output

For each test case there should be single line of output answering the question posed above.

Sample Input

7
12
0

Sample Output

6
4

裸的欧拉函数，因为n的数据比较大，不用筛选法打欧拉函数表，直接用公式：

　　 $LaTeX: phi(n) = n * (1 - frac{1}{p_1})*(1 - frac{1}{p_2}) ... *(1-frac{1}{p_k})$

 1 //2016.8.17
 2 #include<iostream>
 3 #include<cstdio>
 4 
 5 using namespace std;
 6 
 7 int phi(int n)
 8 {
 9     int ans = n;
10     for(int i = 2; i <= n; i++)
11     {
12         if(n%i==0)
13         {
14             ans -= ans/i;
15             while(n%i==0)
16                 n /= i;
17         }
18         if(n == 1)break;
19     }
20     return ans;
21 }
22 
23 int main()
24 {
25     int n;
26     while(cin>>n&&n)
27     {
28         cout<<phi(n)<<endl;
29     }
30 
31     return 0;
32 }