1. 오일러의 phi 함수(Euler's phi function, totient function) $\varphi(n)$은 1부터 n까지의 자연수 중에서 n과 서로소인 자연수의 개수로 정의한다. 그 성질과 응용이 매우 다양하고 또 매우 어려운데... 하나하나 파고들면 끝도 없으니까 문제 풀면서 익히기로 하자 2. 구현 예시1 - 가장 간단한 구현 가장 간단한 방법은 1이상 n이하의 자연수 중에서, n과 서로소인 것의 개수를 세보면 된다. 그러니까 1이상 n이하의 자연수 중에서 n과 최대공약수가 1인 자연수의 개수가 n이하에서 몇개인지 세보면 된다. 유클리드 호제법을 이용해서 최대공약수를 구하는 함수를 만들고, def gcd(a,b): while b != 0: a,b = b,a%b return a 2부터 ..
1. 최대공약수 두 자연수 a,b가 공통으로 가지는 약수중에서 가장 큰 약수를 최대공약수라고 부른다. 중요한 성질중 하나는 최대공약수의 약수는 a,b의 공약수이다. 2. 유클리드 호제법 두 양의 정수 a,b (a>b)에 대하여 a = bq + r ( r은 0이상 b 미만)이라고 하면, a,b의 최대공약수는 b,r의 최대공약수와 같다. 즉, gcd(a,b) = gcd(b,r)이다. 만약 r=0이라하면, a,b의 최대공약수는 b이다. 3. 유클리드 호제법 활용 단 1번만 사용해서는 그 진짜 힘을 알 수 없다. a = bq + r이면 a,b의 최대공약수는 b,r의 최대공약수와 같다 b를 r로 나눠서 b = rq2 + r2라는 식을 얻는다면, 결국 b,r의 최대공약수는 r,r2의 최대공약수와 같다. 여기서 r을..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
