거의 안나온다
오일러 피 함수 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻합니다.
서로소 공약수가 1 이외에 없음
P[6] = 1~6범위 서로소 자연수 개수
- 정답은 1, 5로 2개이다.
- 2는 6과 1이외에 2라는 공약수가 있다.
오일러 피 함수의 원리
- 구하고자 하는 오일러 피의 범위만큼 배열을 초기화
- 2부터 시작해 현재 배열의 값과 인덱스가 같으면(=소수일 때) 현재 선택된 숫자(k)의 배수에 해당하는 수를 배열에 끝까지 탐새갛며 P[i] = p[i]/k 연산을 수행한다(i는 K의배수)
- 배열의 끝까지 2를 반복하여 오일러 피 함수를 완성한다.
