컴퓨터 공학/알고리즘 (2) 썸네일형 리스트형 [C++] 에라토스테네스의 채(The Sieve of Eratosthenes) [C++] 에라토스테네스의 채(The Sieve of Eratosthenes) 소수(Prime Number)는1과 자기 자신밖에 약수가 없다는 특징 때문에 암호학에서 자주 사용되는 방법이기도 하고, 소인수 분해에서도 사용된다.어떤 수를 입력받아서 소수인지 아닌지 판별하는 방법은 1을 제외하고, 입력받은 수 보다 작은 수로 약분이 되는지를 모두 검사하면 된다. 그렇다면 만약에 누군가가 1부터 100사이의 소수를 모두 출력하라고 한다면, 1부터 100사이의 수를 모두다 이처럼 검사할 것인가? 가능은 하지만 너무 오래걸린다.이런 상황에서는, 1부터 N까지의 모든 소수를 구할 수 있는 "에라토스테네스"의 채 알고리즘을 사용하면 된다. 이 알고리즘의 원리는 소수와 어떤 수의 곱은 반드시 소수가 아님을 이용한 것인.. [C++] 두 수의 최대공약수와 최소공배수 (유클리드 호제법) [C++] 최대공약수와 최소공배수와의 관계 (유클리드 호제법) 알고리즘 문제를 풀다보면, 두 수의 최대공약수나 최소공배수가 필요한 상황이 생긴다. 이러한 상황에서는, 최대공약수만 구하더라도 최소공배수를 알 수 있기 때문에 최소공배수를 구하는 법만 알고있으면 된다. 최소공배수를 구하는 방법은 여러가지가 있지만, 컴퓨터 알고리즘에는 유클리드 호제법으로 구하는 것이 가장 빠르고 많이 사용되는 방식이다. #include using namespace std; int gcd(int a, int b) { int r; while (b != 0) { r = a % b; a = b; b = r; } return a; } int main() { int a, b; cin >> a >> b; cout >> GCD(4, 8) >.. 이전 1 다음
