Poj Solution 2407

http://poj.org/problem?id=2407

import java.util.Scanner;   
import java.util.Arrays;
public class Main {   
 // ���1��n-1��n���ʵ���ĸ���,��������
static int eular(int n)
{
    int ret = 1,i;
    for (i = 2;i * i <= n;i++)
        if (n % i == 0)
        {
            n /= i;
            ret *= (i - 1);
            while (n % i == 0)
            {
                n /= i;
                ret *= i;
            }
        }
    if (n > 1)
        ret *= (n - 1);
    return ret;
}


 public static void main(String[] args) {   
    Scanner sc = new Scanner(System.in);   
   
    while(sc.hasNext()){
     int n=sc.nextInt();
     if(n==0) break;
     System.out.println(eular(n));
   }
  }
}  

											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *