k) = 1
-
[백준][Kotlin]11689번 GCD(n, k) = 1백준 2023. 3. 27. 19:16
해당 문제는 입력받은 자연수 n에 대하여 서로소(공약수가 1만 존재) 의 개수를 출력하는 문제입니다. 해당 문제는 오일러 피를 이용하면 쉽게 작성 할 수 있는 문제였습니다. 오일러 피 함수의 원리 첫번째 구하고자 하는 오일러 피의 범위만큼 배열을 초기화 한다 두번째 2부터 시작하여 현재 배열의 값 과 인덱스가 같으면(=소수일 때) 현재 선택된 숫자(k)의 배수에 해당하는 수를 배열에 끝까지 탐색하여 p[i] = p[i]-p[i]/k 연산을 수행한다(i는 k의 배수) 세번째 배열의 끝까지 두번째 과정을 반복하여 오일러 피 함수를 완성한다. 상기 개념을 이용하여 코드를 작성하였습니다. (배열은 사용하지 않고 두번째, 세번째 과정을 이용하여 작성하였습니다.) 하기는 작성한 코드와 제출 결과 입니다. impor..