CodingTEST
2023. 8. 15.
[백준 11689] GCD(n, k) = 1 (JAVA)
백준 11689번 문제 - GCD(n, k) = 1 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 분석 1부터 N까지 수 중에서 최대공약수가 1인 수의 개수를 출력해라 GCD(n,k) : n하고 k의 최대 공약수 해결 키 포인트 정수론 - 서로소 개수 : 오일러 피 메모리, 시간이 여유롭지 않다 메모리: 배열로 값을 따로 저장하지 않고 푼다 시간: N의 약수 이용한다 | N의 제곱근까지만 확인한다. 처음에 헷갈렸던 것 1~1까지 최대 공약수 수는 왜 1인가?: 문제를 보면 N도 포함해서 최대공약수가 1인 수를 출력하는 것 → 즉, 1이 입력되면 자기 ..
![[백준 11689] GCD(n, k) = 1 (JAVA)](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/crOlD7/btsrgp7aJlQ/0KKuDPgIf3zdjKyGgUkl20/img.jpg)