POJ 2407 Relatives 欧拉函数（不打表）

Relatives

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

算法分析：

裸的欧拉函数，不过打表不行，会超内存，数据很水，挨个求就行。

代码实现

#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<cctype>  
#include<cmath>  
#include<iostream>  
#include<sstream>  
#include<iterator>  
#include<algorithm>  
#include<string>  
#include<vector>  
#include<set>  
#include<map>  
#include<stack>  
#include<deque>  
#include<queue>  
#include<list>  
using namespace std;  
const double eps = 1e-8;  
typedef long long ll;  
typedef unsigned long long ULL;  
const int INF = 0x3f3f3f3f;  
const int INT_M_INF = 0x7f7f7f7f;  
  
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};  
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};  
const int MOD = 1e9 + 7;  
const double pi = acos(-1.0);  
const int MAXN=5010;  
const int MAXM=100010;
using namespace std;
ll phi(ll n)
{
    ll res=n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            res=res-res/i;
            do{
                n/=i;
            }while(n%i==0);
        }
    }
    if(n>1) res=res-res/n;
    return res;
}



int main()
{
   
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0) break;
        cout<<phi(n)<<endl;
    }
    return 0;
}