Table of Contents 개요 오일러 피 함수 구현 오일러의 정리 문제 1. 개요 오일러 피 함수는 정수론에 등장하는 함수로서 n 이하의 자연수 중 n과 서로소인 수의 개수를 구하는 함수입니다. 오일러의 정리와 함께 쓰이기도 하고, 단독으로 사용되기도 합니다. 이 글은 독자가 소수를 구하는 알고리즘 중 에라토스테네스의 체를 안다고 가정하고 설명하기 때문에 해당 알고리즘을 모르시는 분은 에라토스테네스의 체 설명을 보고 오시는 걸 추천합니다. 2. 오일러 피 함수 구현 오일러 피 함수란, n 이하의 자연수 중 n과 서로소인 수의 개수를 구하는 함수입니다. n의 소인수 p들에 대해서 아래의 식을 계산하면 오일러 피 함수 값을 얻을 수 있습니다. 위의 식을 구현하기 편하게 정리하면 아래와 같이 됩니다. ..
Table of Contents 개요 ( 프로그래밍에서의 페르마의 소정리 ) 페르마의 소정리로 잉여역수 구하기 구현 나눗셈 연산에 적용 문제 1. 개요 ( 프로그래밍에서의 페르마의 소정리 ) modular 연산의 합동 관계) 두 정수 A,B 에 나눗셈을 적용하여 A/B를 계산하면 몫과 나머지가 나옵니다. 이 때, Q는 몫 R은 나머지라고 하겠습니다. A/B = Q...R A = B*Q + R 보통은 Q를 사용하는 경우가 많지만, R만을 필요로 하는 경우들도 있습니다. 그런 경우들을 위해서 정수론에선 mod 로 불리는 연산자를 사용합니다. 위의 경우를 mod로 표현하면 아래와 같이 됩니다. 위의 식은 'A를 B로 나눈 나머지와, R을 B로 나눈 나머지가 같다.'라는 뜻이 됩니다. A와 R이 법 B에 대해 ..
Table of Contents 개요 유클리드 호제법 시간복잡도 최대공약수에 대해 알아둬야 할 것 문제 1. 개요 두 수 n, m 의 최대공약수를 구할 때, 유클리드 호제법을 이용하면 시간복잡도 O(log(n+m))만에 구할 수 있습니다. 2. 유클리드 호제법 gcd(n,m) = gcd(n-m,m), 그리고 더 나아가 gcd(n,m) = gcd(n%m,m) 임을 이용해 최대공약수를 빠르게 찾는 방법입니다. (n,m 은 자연수) (편의상 n, m 의 최대공약수 = gcd(n,m) 으로 표현하겠습니다.) n,m 은 자연수이고 n%m!=0 일 때, gcd(n,m) = gcd(n%m,m)이다. 증명 g = gcd(n,m), k = gcd(n%m,m), x = n을 m으로 나누었을 때 몫이라고 하겠습니다. (n ..
Table of Contents 개요 단순한 방법 최적화 문제 1. 개요 프로그래밍 문제를 해결하다 보면 소수를 활용해야 하는 경우가 종종 발생하는데, 그 중에서도 특정한 값 N 이하의 소수를 모두 찾아야 하는 경우가 꽤 많습니다. 그럴 때 초,중학교 수학 시절 노가다 취급했던 에라토스테네스의 체가 꽤 좋은 방법이 되어줍니다. (여기에서의 소수는 양의 약수가 1과 자기 자신뿐인, 1보다 큰 자연수를 의미합니다.) 2. 단순한 방법 에라토스테네스의 체를 잊으신 분들을 위해, 그 방법을 그대로 적용한 알고리즘을 소개해 드리면 다음과 같이 됩니다. -------------------------------------------------------------------------------------------..