알고리즘
최대공약수 알고리즘, 유클리드의 호제법 +최소공배수 구하기
1. 유클리드 호제법이란 두 자연수의 최대공약수를 구하는 알고리즘 중 하나 유클리드의 저서 《기하학원본》에 기재되어 있는 최대공약수를 구하는 방법 호제법 또는 연제법 이라고 한다 사용되는 성질 a를 b로 나눈 나머지 = c 이면 a, b의 최대공약수는 b, c의 최대공약수와 같다 알고리즘 두 자연수 또는 다항식 a,b의 최대공약수를 구하는 데 있어, 자연수일 때는 a > b, 다항식일 때는 a의 차수가 b의 차수 이상이라 하고, 다음과 같이 나눗셈을 실행한다 b를 c로 나눈 나머지 = c' 를 구하고 c'를 d로 나눈 나머지 = ... 위 과정을 반복하여 나머지가 0이 되었을 때의 '나누는 수'가 a와 b의 최대공약수이다. 2. 예시 78696과 19332의 최대공약수 구하기 78696＝19332×4＋1..
소수 구하기, 에라토스테네스의 체
1. 가장 기본적인 방법 자연수 x가 소수인지 판별하기 위해서 생각할 수 있는 가장 간단한 방법 x를 2 ~ n-1까지의 모든 수로 나누어 보고, 나누어 떨어지는 수가 존재하는지 확인하는 것 O(n)의 시간복잡도를 가지고 있다 bool IsPrime(int num) { for(int i = 2; i < num; ++i) { if(num % i == 0) { return false; } } return true; } 2. 제곱근을 이용하는 방법 x를 2 ~ √x까지의 모든 수로 나누어 보고, 나누어 떨어지는 수가 존재하는지 확인하는 것 O(√n)의 시간복잡도를 가지고 있다 bool IsPrime(int num) { int sqrtNum = (int)Math.Sqrt(num); for (int i = 2; i