Softonic

최대공약수 계산기

단계 1 / 2 최대공약수(GCF/GCD)
다음

최대공약수(GCD 또는 HCF라고도 함)는 어떤 수의 집합에 속한 모든 수를 나머지 없이 나누는 가장 큰 정수입니다. 두 개 이상의 양의 정수를 입력하면 이 계산기는 유클리드 호제법으로 그 최대공약수를 바로 구해 줍니다. 결과를 사용해 숙제를 확인하거나 84/144 같은 분수를 7/12로 약분할 수 있습니다.

최대공약수 계산 방법

  1. 1

    정수 입력하기

    두 개 이상의 양의 정수를 쉼표, 공백 또는 줄바꿈으로 구분해 입력합니다.

  2. 2

    도구가 유클리드 호제법을 적용합니다

    나머지가 0이 될 때까지 (a, b)를 (b, a mod b)로 반복해서 바꿉니다.

  3. 3

    최대공약수 확인하기

    표시된 결과가 입력한 수들의 최대공약수이며, 유클리드 호제법으로 계산됩니다.

유클리드 호제법

a ≥ b > 0일 때 gcd(a, b)를 구하려면 다음과 같이 합니다.

while b ≠ 0:
    (a, b) ← (b, a mod b)
return a

세 개 이상의 수에 대해서는 항등식 gcd(a, b, c) = gcd(gcd(a, b), c)를 적용합니다.

계산 예시: 최대공약수(84, 144)

단계 나눗셈 나머지
1 144 ÷ 84 = 1 r 60 60
2 84 ÷ 60 = 1 r 24 24
3 60 ÷ 24 = 2 r 12 12
4 24 ÷ 12 = 2 r 0 0

마지막으로 나온 0이 아닌 나머지는 12이므로 gcd(84, 144) = 12이며, 84/144는 7/12로 약분됩니다.

최대공약수가 1일 때

gcd(a, b) = 1이면 두 수는 서로소입니다. 15와 28은 둘 다 소수가 아니지만 서로소이며, 바로 이 성질 때문에 15/28은 더 이상 약분할 수 없습니다.

최소공배수와의 관계

gcd(a, b) × lcm(a, b) = |a × b|가 성립합니다. 따라서 하나를 구하면 다른 하나도 자연스럽게 얻을 수 있습니다.

자주 쓰이는 사례

  • 분수를 기약분수로 약분하기.
  • 직사각형을 빈틈없이 덮는 가장 큰 정사각형 타일 크기 구하기.
  • 기어비와 풀리 지름을 간단한 비로 줄이기.
  • 모듈러 연산: 서로소인 수의 쌍은 서로를 법으로 하여 역원을 가집니다.

자주 묻는 질문

모두 같은 값을 가리키는 세 가지 이름입니다. GCF(greatest common factor)는 미국 학교에서, GCD(greatest common divisor)는 수학과 컴퓨터 과학에서, HCF(highest common factor)는 영국 교육과정에서 주로 쓰입니다. 한국어로는 모두 최대공약수에 해당합니다.

음수는 건너뜁니다. 계산에는 양의 정수만 포함됩니다. 음수를 포함하려면 절댓값을 입력하세요(예: -84 대신 84).

n이 양수일 때 n입니다. 0은 모든 정수로 나누어떨어지므로 n과의 최대공약수는 n 자신입니다. gcd(0, 0)은 보통 0으로 정의합니다.

저장되지 않습니다. 입력한 숫자는 결과를 계산하기 위해서만 서버로 전송되며, 단계를 이동할 때 페이지 링크에도 포함될 수 있습니다.

관련 도구

브라 사이즈 변환기

UK, US, EU, 프랑스/벨기에, 호주/뉴질랜드 브라 사이즈를 표준 밴드·컵 변환표로 서로 변환합니다.

볼트 원 계산기

등간격 볼트 구멍의 PCD, 각도 간격, 정확한 X/Y 좌표를 계산하고 회전, 중심 오프셋, CSV 내보내기를 설정하세요.

CPU와 GPU 병목 현상 계산기

동일한 게임 장면에서 측정한 CPU와 GPU 프레임 시간을 비교하고, FPS 상한을 추정하고, 허용 오차를 적용하여 결과가 무엇을 입증할 수 있고 무엇을 입증할 수 없는지 알아보세요.

지붕 트러스 계산기

건물 길이, 지지점 간 경간, 물매와 처마 돌출을 바탕으로 트러스 위치, 균등 간격, 박공 높이와 지붕선 길이를 계산합니다.

모래 계산기

직사각형, 원형, 삼각형 또는 면적을 알고 있는 공간에 필요한 모래의 마감·구매 부피, 중량, 포대 수와 자재비를 계산합니다.

고양이 사료 계산기

고양이의 체중, 나이, 활동량에 따라 하루 필요 칼로리와 사료 급여량을 계산하세요. 건식, 습식, 혼합 급여 모두 사용할 수 있습니다.

이 도구는 다른 언어로도 제공됩니다