# SGU102 Coprimes（欧拉函数）

## 102. Coprimes

• time limit per test: 0.25 sec.
• memory limit per test: 4096 KB

For given integer N ($1<=N<=10^{4}$) 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.

### Sample Input

9

### Sample Output

6

### 链接

https://cn.vjudge.net/problem/SGU-102

### 代码

StatusAccepted
Time15ms
Memory1848kB
Length372
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int gcd(int a, int b)
{
int c;
while (b != 0)
{
c = a % b;
a = b;
b = c;
}
return a;
}

int main()
{
int n, cnt = 1;
scanf("%d", &n);
for (int i = 2; i < n; ++i)
if (gcd(n, i) == 1)
cnt++;
printf("%d\n", cnt);
}
StatusAccepted
Memory1860kB
Length360
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
int n, ans, p;
scanf("%d", &n);
ans = n, p = 2;
while (n != 1)
{
if (n % p == 0)
{
ans = (ans / p * (p-1));
while (n % p == 0)
n /= p;
}
p++;
}
printf("%d\n", ans);
}

The end.
2018-06-08 星期五