녕의 학습 기록
백준_11689 GCD(n, k) = 1 (오일러 피 함수) 본문
반복문이 끝난 뒤 temp를 확인해 소인수가 남았는지 체크 후,
남아있으면 마저 해당 소인수의 배수인 서로소를 제거하는 것에 주의
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BJ_11689_GCD {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long n = Long.parseLong(br.readLine());
long result = n;
long temp = n;
for (int i=2; i<=Math.sqrt(n); i++) {
if (temp%i == 0) { // 소인수이면
result = result - result/i;
while(temp%i == 0) { // temp에서 계산 끝난 소인수 제거
temp = temp/i;
}
}
}
if(temp > 1) { // 소인수가 남아있으면
result = result - result/temp;
}
System.out.println(new StringBuilder().append(result));
}
}
11689번: GCD(n, k) = 1
자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
'Algorithm > Algorithm 문제' 카테고리의 다른 글
백준_1850 최대공약수 (유클리드 호제법) (0) | 2024.02.07 |
---|---|
백준_1934 최소공배수 (유클리드 호제법) (1) | 2024.02.06 |
백준_1016 제곱ㄴㄴ수 (에라토스테네스의 채) (0) | 2024.02.04 |
백준_1747 소수&팰린드롬 (에라토스테네스의 채) (0) | 2024.02.03 |
백준_1456 거의 소수 (에라토스테네스의 채) (1) | 2024.02.02 |