[ Do it! 알고리즘 코딩 테스트 ] 정수론 오일러 피

 

🔷 오일러 피( Eluer's phi )?

해당 기호를 사용하며 phi라고 읽으며 대표적으로 서로소 관련 문제에서 사용된다.

 

🔷P[N] ?

1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다.

 

💡 서로소란?

두 수 사이의 관계에서 공통되는 약수가 최대 1이며 1 밖에 없는 수를 뜻한다. 

서로소의 예시로는 아래와 같이 확인 할 수 있다.

 

◾ 5의 약수 : 1 , 5

◾ 6의 약수 : 1 , 2 , 3 , 6

◻ 5와 6의 최대 공약수는 1이며 두 수가 일치하는 수는 1이므로 서로소라고 할 수 있다.

 

🔷  오일러 피의 원리

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

🔻 2부터 시작해서 인덱스가 같을 때(소수일 때) 현재 선택된 숫자의 배수에 해당되는 수(K)의 배열 끝까지 탐색 후 

P[i] = P[i] - P[i]/K  수행

🔻 배열 끝까지 반복하여 오일러 피 함수 완성

 

즉 에라토스테네스의 체에서 배수를 지우는 부분만 P[i] = P[i] - P[i]/K 치환하는 방식이다.

 

🔷  오일러 피의 과정

2의 배수 

3의 배수 

5의 배수 

 

참고 사이트

https://blog.naver.com/yyhjin12/222864062441