SGU102 Coprimes

102. Coprimes

time limit per test: 0.5 sec.
memory limit per test: 4096 KB

For given integer N (1<=N<=10⁴) find amount of positive numbers not greater than N that coprime with N. Let us call two positive integers (say, A and B, for example) coprime if (and only if) their greatest common divisor is 1. (i.e. A and B are coprime iff gcd(A,B) = 1).

Input

Input file contains integer N.

Output

Write answer in output file.

Sample Input

Sample Output

6
题解：直接枚举。。。睡觉之前果断怒水一题啊，嘿嘿。WA了一次，木有考虑到 gcd(1,1)=1的情况。。。

View Code

 1 #include<stdio.h>
 2 long gcd(long a,long b)
 3 {
 4     if(b==0) return a;
 5     else
 6     return gcd(b,a%b);
 7 }
 8 int main(void)
 9 {
10     long n,i,ans;
11     ans=0;
12     scanf("%ld",&n);
13     for(i=1;i<=n;i++)
14     if(gcd(i,n)==1)
15     ans++;
16     printf("%ld\n",ans);
17     return 0;
18 }