# 오일러 피

* 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다.



### 오일러 피 함수 구현하기

#### Question

![](https://2669959621-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxncaDDrGpdjhVy86HbwM%2Fuploads%2FfMC9bM8Qm70X7SUHJASh%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-08-02%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%202.54.25.png?alt=media\&token=1d67148a-4d24-4e28-ba92-c9cacd4618a3)

#### Code

```java
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class N41_P11689_오일러_피_함수 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());
        long result = n;

        for (long p = 2; p <= Math.sqrt(n); p++) {
            if (n % p == 0) {
                result = result - result / p;
                while (n % p == 0) {
                    n /= p;
                }
            }
        }
        if (n > 1) {
            result = result - result / n;
        }
        System.out.println(result);
    }
}

```

#### Insight

#### Idea

* 수학
* 정수론
* 오일러 피 함수&#x20;

#### reference
