Euler's totient function (피 함수)

알고리즘 공부하면서 정수론을 처음 접해보는데 데였다.. 그렇지만 확실히 재미있었다. 나중에 증명과정도 하나하나 공부하고 싶다는 생각이 들었다. 오늘 공부한 내용은 오일러의 토티엔트 함수이다. 다른 말로 피 함수라고 불린다고 한다. 함수의 기능은 다음과 같다. 정수 m이 주어졌을 때 1 <= x < m 인 x 중 m과 서로소인 정수의 개수 1부터 21까지 피 함수 값을 구한 것을 나열한 사진이다. 컴퓨터를 통해서 피 함수를 구하기 위해서는 이 피 함수를 일반화시켜야 한다. 그 전에 몇가지 짚어야 할 사항이 있다. 소수 p에 대하여 서로소 a와 b에 대하여 (중국인의 나머지 정리를 통해서 증명할 수 있다고 하는데 이 부분은 더 공부해야할 것 같다.) 위의 성질들을 종합하여 구한 정수 n에 대한 pi 함수는 다음과 같다. # 구현 코드 int phi(int n) { int result = n; for (int i = 2; i * i <= n; i++) { if (n % i == 0) { ...

원문링크 : Euler's totient function (피 함수)