[C++/CPP] C++ 코딩테스트용 gcd / lcm, 최대공약수, 최소공배수

Visual Studio에 <bits/stdc++.h> 헤더파일 추가하기

출처:https://hkhan.tistory.com/36

[C++] Visual Studio에 <bits/stdc++.h> 헤더파일 추가하기

stdc++.h

0.00MB

C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.38.33130\include

위 경로에서 " 14.33 .31629 "는 Visual Studio 버전이며 각자 다른 숫자일 수 있으니 불안하다면 각 폴더에 있는 include에 bits 폴더 복사 후 붙여넣기 해준다.

위 경로에서 "bits" 폴더 생성 후 "stdc++.h" 파일 넣는다.

#include<bits/stdc++.h>
// include 신경쓰지 않고 코딩에만 집중

int main() {
	// logic
}

 

C++ 온라인 컴파일러 사이트

1. https://replit.com/~
2. https://www.onlinegdb.com/online_c++_compiler
3. https://cpp.sh/
4. https://www.tutorialspoint.com/compile_cpp_online.php

GCD / LCM

#include<bits/stdc++.h>

using namespace std;

int gcd(int a, int b) {
	if (a == 0) return b;
	return gcd(b % a, a);
}

int lcm(int a, int b) {
	return (a * b) / gcd(a, b);
}

int main() {
	int a = 10, b = 12;
	cout << lcm(a, b) << '\n';
	return 0;
}

// result
// 60

이 코드는 두 개의 정수 a와 b에 대한

최대공약수(Greatest Common Divisor, GCD)와

최소공배수(Least Common Multiple, LCM)를 구하는 함수를 포함하고 있습니다.

그리고 이 함수들을 사용하여 주어진 두 정수의 최소공배수를 출력하는 간단한 프로그램입니다.

먼저, 함수 `gcd`는 두 정수의 최대공약수를 계산하는 함수입니다. 

최대공약수는 두 수를 나눌 수 있는 가장 큰 양의 정수입니다. 

이 함수는 재귀적으로 호출되며, a가 0이 될 때까지 b를 a로 나누고,

 나머지를 새로운 a로 하여 계속해서 호출됩니다. 

최종적으로 a가 0이 되면 b가 최대공약수가 됩니다.

int gcd(int a, int b){
    if(a == 0) return b;
    return gcd(b % a, a);
}

다음으로, 함수 `lcm`은 두 정수의 최소공배수를 계산하는 함수입니다. 

최소공배수는 두 수의 곱을 최대공약수로 나눈 값입니다. 

따라서 `lcm` 함수는 `(a * b) / gcd(a, b)`로 정의되어 있습니다.

int lcm(int a, int b){
    return (a * b) / gcd(a, b);
}

마지막으로, `main` 함수에서는 두 정수 a와 b를 초기화하고, 

`lcm` 함수를 호출하여 최소공배수를 계산하고 출력합니다.

int main(){
    int a = 10, b = 12;
    cout << lcm(a, b) << '\n';
    return 0;
}

따라서 위 코드는 a와 b가 각각 10과 12일 때의 최소공배수를 계산하고 출력하는 예제입니다. 

결과적으로는 60이 출력될 것입니다.