2011/10/06 썸네일형 리스트형 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.. 더보기 이전 1 다음