본문 바로가기

Discrete Math/Number theory

Euclidean algorithm (유클리드 호제법) 두 자연수 a,b 의 GCD(Great Common Divisor)인 d를 기호로 (a,b)로 나타내면 d=(a,b)이다. a,b는 모두 GCD인 d로 나누어 떨어지므로 a-b도 d로 나누어 떨어진다. ※ d는 a-b와 b의 GCD이다. 이와 같은 과정을 반복하여 두 수의 GCD를 구하는 방법이 Euclidean algorithm!! #include using namespace std; int main(void) { int i,j,GCD; cout > i; cout > j; while(1) { if(i==j) { GCD = i; cout 더보기
소수판별법 1 보다 큰 자연수 n 에 대하여 √n 보다 작거나 같은 모든 소수가 n을 나누지 못하면 n은 소수이다. 대우와 귀류법을 통한 증명) 대우명제를 부정 -> n이 합성수이면 n은 √n보다 작거나 같은 약수를 갖지 않는다. n=ab(ab는 양의정수이고 1이 아니다) 가정에 의하면 2 ≤ a ≤ b √n, b > √n a x b > √n x √n n > n -> 여기서 모순이 발생한다. 따라서 n이 소수가 아니라면 n의 약수 중에서 √n보다 작거나 같은 소수가 존재한다. 그러므로 자연수 n이 √n 이하의 어떤 소수로도 나누어 떨어지지 않으면 n 은 소수이다. #include #include using namespace std; int main(void) { int N,i; cout > N; fo.. 더보기
Sieve of Erathosthenes(에라토스테네스의 체) 그리스의 수학자이인 에라토스테네스가 고안한 소수를 찾는 방법으로 특정 양의 정수보다 작은 소수를 찾아내는 방법이다. 자연수 n보다 작은 소수 p를 구하는 방법. How to) 1. 1을 지우고 p를 2로 놓는다. 2. p를 남기고 n보다 작은 p의 배수를 모두 제거한다. 3. 아직 제거되지 않은 p보다 큰 수 중에서 최소의 수를 다시 p로 놓는다. 4. 다시 2. 로 돌아간다. 프로그래밍 구현 예) #include using namespace std; int main(void) { int i; cout > i; while(i) { for(j=2;j 더보기