这是SGU 102的一份题解

题目要求找不大于N的自然数中与N互质的数，N的范围是1到10000.

由于N的范围小，可以用直接枚举的方法做，辗转相除求GCD。

但要考虑特殊情况：N=1时，1和它本身互质。

如果数据范围变大，如10^9，则不能用枚举。

用分解质因数的方法做。

用唯一分解定理： n>=2,设p1,p2,p3,......,pn是n的素因子，则不大于它的自然数中与它互质的有 n*(1-1/p1)*(1-1/p2)*......*(1-1/pn)个

n=1，n没有素因子，个数为1（即其本身）

代码如下：

#include "stdio.h"int GCD(int a,int b){	if(!b)return a;	else return GCD(b,a%b);}int main(){	int n,i,cnt=0;	scanf("%d",&n);	for(i=1;i<=n;i++){		if(GCD(n,i)==1)cnt++;	}	printf("%d",cnt);	return 0;}