Haekt‘s log

1707~1783 년 레온하르트 오일러가 만든 함수로, p(n) 는 1 부터 n 까지의 정수중 n 과 서로소인 정수의 개수를 뜻한다. ex) p(4) = 2 : 1 3 자신과의 서로소 1 ,3 -> 2개 n이 소수일때 아래의 공식이 성립 p(n^x) : n^x - n^(x-1) 만약 p(20) 과 같은 소수가 아닌 수가 나올 경우. p(2^2) * p(5) 처럼 소수로 바꾸면 공식을 사용할 수 있어, 보다 더 쉽고 빠르게 풀 수 있다. ex) p(2^2) = 2^2 - 2 = 2 p(7) = 7^1 - 7^0 = 6 p(252) = p(2^2) * p(3^2) * p(7) = ( 4 - 2 ) * ( 9 - 3 ) * ( 7 - 1 ) = 72