Posted on 2010-08-17 13:24
Brian 阅读(191)
评论(0) 编辑 收藏 引用 所属分类:
SGU
题目简单翻译：对于给出的整数 N (1<=N<=10
4) ，找出所有不大于N且与N互质的正整数
个数。
两个正整数A和B互质的意思是它们的最大公约数是1。现看一下百度百科上关于
质数的定义吧。
当我采用直接数的办法AC后，我发现跟质数完全没有关系。
#include<stdio.h>
int gcd(int m,int n) // greatest common divisor
{
int r=m%n;
while(r) // 辗转相除法，TAOCP的第一个算法
{
m=n;
n=r;
r=m%n;
}
return n;
}
int main()
{
int N,c=0,i=1; // must start with 1 !
scanf("%d",&N);
for (; i<=N; i++)
if (gcd(N,i)==1) // question hint
c++;
printf("%d",c);
return 0;
}
// 102 .C Accepted 0 ms 0 kb