문제

✏️https://www.acmicpc.net/problem/11689

해설

오일러 피
P[i] = P[i] - P[i]/i

GCD는 최대 공약수이다.

최대 공약수가 1이라는 것은 두 수 n, k 의 공약수가 1개라는 소리다. 즉 서로소 라는 뜻이다.

이 문제는 1부터 입력받은 값까지 중에서 서로소인 수를 구하는 문제이다.

1. 에리토스 테네스의 체를 통해 범위를 2부터 Math.sqrt(key)까지 포문을 돌린다.

        for(long i =2; i<= Math.sqrt(key); i++)

2. 이후 해당 값이 key값과 나누어 떨이진다면 해당 수는 key값의 약수라는 소리다.

            if(count % i == 0){
                result = result - result/i;
            }

3. 조건 속에서 while문을 통해 해당 값을 key값과 더이상 나누어 떨어지지 않을때까지 몫을 구한 후 해당 값을 key값에 저장한다.

                while(count % i == 0){
                    count /= i;
                }

4. 만약 약수가 첫 포문의 조건 Math.sqrt(key)보다 큰 수일 경우를 대비 해서 다음 조건과 식을 추가한다.

if( count>1 ){
	result = result - result/count;
}

5.이후 결과값을 출력한다.

코드

import java.io.*;

public class J11689_0 {
    public static void main(String[] args) throws IOException {
        BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));

        long key = Long.parseLong(buffer.readLine());

        long count = key;
        long result = key;

        for(long i =2; i<= Math.sqrt(key); i++){
            if(count % i == 0){
                result = result - result/i;
                while(count % i == 0){
                    count /= i;
                }
            }
        }
        
        if( count>1 ){
            result = result - result/count;
        }

        System.out.println(result);
    }
}