정수론 : 오일러 피

오일러 피

오일러 피 함수 P[N] = 1부터 N까지 범위에서 N과 서로소인 자연수의 개수

(서로소 : 공약수가 1 이외에 없는 수)

 

1. 구하고자 하는 오일러 피의 범위만큼 배열 초기화

2. 2부터 시작해 현재 배열의 값과 인덱스가 같으면(= 소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열의 끝까지 탐색하며 P[i] = P[i] - P[i] / K 연산 수행

3. 배열의 끝까지 2번을 반복

 

 

예) P[15]를 구해보자.

1. 15까지의 배열 생성 및 초기화

 

2. 2의 모든 배수마다 P[i] = P[i] - P[i] / K 수행

-> ex) 8 = 8 - (8 /  2)로 4가 됨

 

3. 3의 배수마다 2번 반복

...

배열이 끝날 때까지 반복

 

4. 오일러 피 완성

 

 

* 코딩 테스트에 자주 출제되지는 않지만 원리를 알지 못하면 출제 됐을 때 문제 접근이 어려움