欧拉函数

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1136

对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。
此函数以其首名研究者欧拉命名，它又称为Euler’s totient function、φ函数、欧拉商数等。
例如：φ(8) = 4（Phi(8) = 4），因为1,3,5,7均和8互质。

Input

输入一个数N。(2 <= N <= 10^9)

Output

输出Phi(n)。

Input示例

8

Output示例

4

分析：

欧拉函数：就是求出在区间[1, n-1]中有m个数与n互质，求出m的值

欧拉函数的求法：如果a1,a2,a3……是n的质因子数，那么 m = n * (1 - 1/a1) * (1- 1/a2) * (1- 1/a3)……

互质：2个数之间只有1是他们的公约数

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		in.nextToken();
		int n = (int) in.nval;
		out.println(euler(n));
		out.flush();
	}

	static int euler(int n) {
		int res = n;
		for (int i = 2; i * i <= n; i++) {
			if (n % i == 0) {
				res = res / i * (i - 1);
				while (n % i == 0) {
					n = n / i;
				}
			}
		}
		if (n != 1) {
			res = res * (n - 1) / n;
		}
		return res;
	}
}