문제 설명
오일러 피 함수(φ(n))는 자연수 n에 대해 n과 서로 소인 양의 정수의 개수를 나타냅니다. 예를 들어, φ(1) = 1, φ(2) = 1, φ(3) = 2, φ(4) = 2, φ(5) = 4와 같은 결과를 보여줍니다. 이 문제에서는 주어진 자연수 n에 대해 φ(n)를 계산하는 프로그램을 작성하는 것이 목표입니다.
문제: φ(n) 계산하기
자연수 n이 주어졌을 때, n에 대해 φ(n)를 계산하는 자바 프로그램을 작성하세요. 단, n은 1 이상 10^6 이하의 정수입니다.
입력 형식
- 첫 줄에 자연수 n이 주어집니다.
출력 형식
- n에 대한 φ(n)의 값을 출력합니다.
문제 풀이 과정
문제를 해결하기 위해서는 오일러 피 함수의 정의와 성질을 정확히 이해하고, 이를 효율적으로 계산하는 알고리즘을 설계해야 합니다.
오일러 피 함수의 정의
오일러 피 함수는 다음과 같이 계산됩니다:
φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)
여기서 p1, p2, …, pk는 n의 고유 소인수입니다. 즉, n을 소인수 분해한 결과에 등장하는 소수의 개수와 그들의 곱을 통해 결과를 구할 수 있습니다.
소인수 분해를 통한 φ(n) 계산
자바에서 이 방정식을 사용하여 φ(n)를 계산하기 위한 단계는 다음과 같습니다:
- 입력 받은 n의 초기 값을 설정합니다.
- 2부터 n의 제곱근까지 반복하며 소수를 찾습니다.
- 각 소수 p에 대해 n이 p로 나뉘어지는지 확인하고, 나뉘어지면 n을 p로 나눈 다음, φ(n)에 (1 – 1/p)의 값을 곱합니다.
- 마지막으로, n이 1이 될 때까지 반복합니다.
- 계산한 φ(n)의 값을 출력합니다.
자바 코드 예제
다음은 φ(n)를 계산하는 자바 코드의 예제입니다:
import java.util.Scanner;
public class EulerTotient {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int originalN = n;
double result = n;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
while (n % i == 0) {
n /= i;
}
result *= (1.0 - (1.0 / (double)i));
}
}
if (n > 1) {
result *= (1.0 - (1.0 / (double)n));
}
System.out.println((int)result);
}
}
이 코드는 사용자가 입력한 n의 값에 대해 φ(n)를 계산하여 출력합니다. 소수로 나뉘어지는 경우와 나누어진 후 응답하는 방식으로 φ(n)을 계산하였습니다.
효율성 분석
이 알고리즘의 시간 복잡도는 O(√n)입니다. 왜냐하면 소수를 찾기 위해 n의 제곱근까지 반복해야 하기 때문입니다. 이 방법은 n의 크기가 최대 10^6인 경우도 무리 없이 처리할 수 있습니다. 또한, 공간 복잡도는 O(1)로, 추가적인 메모리 사용이 최소화되어 있어 효율적입니다.
결론
오일러 피 함수는 수론과 알고리즘 문제에서 매우 중요한 개념 중 하나입니다. 이 문제를 해결하는 과정을 통해 소수, 소인수 분해 및 기본적인 수학적 원리에 대한 이해도를 높일 수 있습니다. 자바를 사용한 코딩테스트 준비에 유용한 문제로 기억하시기 바랍니다.