POJ 2407-Relatives(求一个整数的欧拉函数值) - c++编程基础

Relatives Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Submit Status Practice POJ 2407 Appoint description:

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，求出不大于n且与n互素的数的个数。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include
             using namespace std; typedef long long LL; const int inf=0x3f3f3f3f; const double pi= acos(-1.0); int Euler(int n) { int m=floor(sqrt(n+0.5)); int ans=n; for(int i=2;i<=m;i++){ if(n%i==0){ ans=ans/i*(i-1); while(n%i==0){ n/=i; } } } if(n>1) ans=ans/n*(n-1); return ans; } int main() { int n; while(~scanf("%d",&n)){ if(!n) break; printf("%d\n",Euler(n)); } return 0; }