Relatives

--------------------------------------------------------------------------------

Time limit: 1sec. Submitted: 91
Memory limit: 32M Accepted: 41

Source : Waterloo ACM Programming Contest June 1, 2002

--------------------------------------------------------------------------------

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 <stdio.h>
#include <math.h>

int main()
{
long n, num = 0, sum = 0;
int i, j;

while(scanf("%ld", &n) != EOF&&n != 0)
{
sum = n - 1;
for(i = 2;i < n;i ++)
{
if(n%i == 0)
{
sum --;
for(j = i + 1;j < n;j ++)
{
if(j%i == 0)
num ++;
}
sum -= num;
num = 0;
}
}
printf("%ld\n", sum);
}

return 0;
}

貌似有公式的说.........

公式？什么公式呀？

好象是欧拉公式,去baidu一下

看了！是顶点数加面数减棱数等于二！这道题好像是要找有多少个和这个数字没有公约数的数！我实在向不通他们之间 有什么联系啊!

汗,说错了,是欧拉函数........

互质就是没有公约数的意思吧！

通过了！
#include<stdio.h>/*包含头文件*/
int main()/*1~n中与n互质的数的个数*/
{
int m;
while(scanf("%d", &m) != EOF&&m != 0)
{
int euler=m,i;
if (m%2==0)
{
euler/=2;
do{
m/=2;
}while(m%2==0);
}
for (i=3;m>1;i+=2)
{
if (m%i==0)
{
euler-=euler/i;
do{
m/=i;
}while(m%i==0);
}
}
printf("%d\n", euler);
}
return 0;
}

这道题目简单,要是叫我做,我还是会用求最大公约数的函数,然后看看return的是不是1.
代码继续放上来,没去测试,不知道有没有问题.继续C++习惯了哈.
#include<iostream>
using namespace std;
int gcd(int a,int b){
if(b==0)return a;
else return gcd(b,a%b);
}
int main(){
int m,i,c;
while(cin>>m&&m!=0){
c=0;
for(i=1;i<m;i++){
if(gcd(m,i)==1)c++;
}
cout<<c<<endl;
}
}