728x90
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 ≤ 1012)이 주어진다. 출력 GCD(n, k) = 1을 만
spicyrisotto.tistory.com
728x90
'책 > Do it! 알고리즘 코딩 테스트 자바 편' 카테고리의 다른 글
| Day-15 유니온 파인드 (0) | 2024.04.10 |
|---|---|
| Day-14 그래프의 표현 (0) | 2024.04.10 |
| Day-13 확장 유클리드 호제법 (0) | 2024.04.06 |
| Day-13 유클리드 호제법 (0) | 2024.04.04 |
| Day-12 소수 구하기 (0) | 2024.04.04 |
