Algorithm/Algorithm (10) 썸네일형 리스트형 [Algorithm] 유클리드 호제법 1. 개요 - 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나. 2. 방법 1. 입력으로 두 수 m,n(m>n)이 들어온다. 2. n이 0이라면, m을 출력하고 알고리즘을 종료한다. 3. m이 n으로 나누어 떨어지면 n을 출력하고 알고리즘을 종료한다. 4. 그렇지 않으면 m을 n으로 나눈 나머지를 새롭게 m에 대입하고 , m과 n을 바꾸고 3번으로 돌아온다. 3. 구현 - C++ int gcd(int a, int b) { int c; while(b) { c = a % b; a = b; b = c; } return a; } 4. 예시 문제 https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는.. [Algorithm] 에라토스테네스의 체 1. 개요 - 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수(primary number)를 찾는 방법이다. 마치 체를 치듯 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다고 함. - 임의의 자연수 n에 대하여 그 이하의 소수를 찾는 가장 간단하고 빠른 방법. 2. 방법 1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열 한다. 2. 2는 소수이므로 오른쪽에 2를 쓴다. 3. 자기 자신을 제외한 2의 배수를 모두 지운다. 4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. 5. 자기 자신을 제외한 3의 배수를 모두 지운다. ...... 위 과정을 반복하면 구간의 모든 소수가 남는다. 3. 구현 - C++ void Eratos(int n) { /* 만일 n이 1보다 작거나 같으.. 이전 1 2 다음
