POJ2407:Relatives(欧拉函数)

Relatives Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 9411 Accepted: 4453

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

Source

Waterloo local 2002.07.01 MYCode: #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; int euler(int x) {     int res=x;     int i;     for(i=2;i*i<=x;i++)     {         if(x%i==0)         {             res=res*1.0/i*(i-1);             while(x%i==0)x/=i;         }     }     if(x>1)res=res/x*(x-1);     return res; } int main() {     int p;     while(scanf("%d",&p))     {         if(p==0)         break;         int ans=euler(p);         printf("%d\n",ans);     } } // 欧拉函数模板题,可以使用素数表优化.

转载于:https://www.cnblogs.com/java20130725/archive/2012/11/24/3215894.html

相关资源：数据结构—成绩单生成器