728x90 오일러 피2 Day-12 오일러 피 1. 오일러 피 오일러 피 함수 P[N]은 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다. 서로소란 공약수가 1 밖에 없는 수를 의미한다. 2. 오일러 피 원리 오일러 피 함수의 원리는 소수 구하기에서 사용한 에라토스테네스의 체와 비슷하다. 구하고자 하는 오일러 피의 범위만큼 배열을 초기화 2부터 시작해 현재 값이 소수이면, 현재 값의 배수에 해당하는 수에 P[i] = P[i] - P[i] / K 연산을 수행 배열의 끝까지 과정 2를 반복 3. 예제 문제 [11689] GCD(n, k) = 1 (JAVA) # 문제 설명 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 n (1 ≤ n ≤ .. 2024. 4. 7. [11689] GCD(n, k) = 1 (JAVA) # 문제 설명 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 n (1 ≤ n ≤ 1012)이 주어진다. 출력 GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 출력한다. # 정답 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringT.. 2024. 4. 7. 이전 1 다음 728x90
