Greatest Common Factor

Greatest Common Divisor - GCD

Last Updated : 14 May, 2025

The Greatest Common Divisor (GCD) also known as the Highest Common Factor (HCF) is the greatest number that divides a set of numbers without leaving a remainder. For example: GCD of 12 and 18 is 6, as it divides both numbers and is the largest of all their factors.

The GCD of any two numbers is never negative or 0, and the least positive integer common to any two numbers is always 1.

Examples of GCD (Greatest Common Divisor)

12 and 18:
Divisors of 12 are 1, 2, 3, 4, 6 and 12
Divisors of 18 are 1, 2, 3, 6, 9 and 18
The common Divisors are 1, 2, 3 and 6. The greatest common divisor or GCD is 6
30 and 15:
Divisors of 30 are 1, 2, 3, 5, 15 and 30
Divisors of 15 are 1, 3, 5 and 15
The common Divisors are 1, 3, 5 and 15. The greatest common divisor or GCD is 15.
4 and 9:
Divisors of 4 are 1, 2 and 4
Divisors of 9 are 1, 3 and 9
There is only one common divisor 1. Hence GCD is 1.

GCD for Beginners

This section covers the basics of GCD, different methods to find it, its properties, and real-life uses explained in a simple way.

GCD for Aptitude Preparation

Prepare for aptitude exams with shortcut methods, solved examples, and common GCD-related questions.

GCD Practice Questions

Practice GCD problems of varying difficulty, including MCQs to test and improve your problem-solving skills.

GCD for Programmers

Learn how to solve GCD-related problems using code, from basic programs to competitive programming challenges.

Greatest Common Factor

A

amitabhgarg

Improve

Article Tags :

Similar Reads

Greatest Common Factor

Greatest Common Factor or GCF is the largest positive integer that evenly divides two or more integers without leaving a residual. In simple words, the Greatest Common Factor is the largest value that can be used to divide these numbers and get whole numbers.Â Greatest Common Factor is a fundamental

Common divisors of N numbers

Given an array arr[] of N integers. The task is to find all the common divisors of all N integers.Examples Input: arr[] = {6, 90, 12, 18, 30, 18} Output: 1 2 3 6 Explanation: GCD of all the numbers is 6. Now to find all the divisors of 6, we have 6 = 1 * 6 6 = 2 * 3 Hence 1, 2, 3 and 6 the common di

Program to find Greatest Common Divisor (GCD) of N strings

Given an array of string arr[], the task is the Greatest Common Divisor of the given array of string. In strings 'A' and 'B', we say "B divides A" if and only if A = concatenation of B more than 1 times.Find the largest string which divides both A and B. Examples: Input: arr[] = { "GFGGFG", "GFGGFG"

CSES Solutions - Common Divisors

You are given an array of N positive integers. Your task is to find two integers such that their greatest common divisor is as large as possible. Example: Input: N = 5, arr[] = {3, 14, 15, 7, 9}Output: 7Explanation: GCD(14, 7)=7 which is the maximum possible among all the pairs Input: arr[] = {1, 12

Common Divisor Reduction Algorithm

Given two integers x and y. In one step, we have to subtract the greatest common divisor of x and y from x and y each till x â‰¥ 1 and y â‰¥ 1. We have to find the minimum number of repetitions of this step. Examples: Input: x = 36, y = 16Output: 4Explanation: GCD of 36 and 16 is 4, so replace 36 and 16

GCD by Long Division Method

The Greatest Common Divisor (GCD), or Highest Common Factor (HCF), of two or more integers, is the largest positive integer that divides each of the integers without leaving a remainder. For example, the GCD of 12 and 18 is 6. In this article, we will explore using the Long Division Method, also kno

Divisors in Maths

In Mathematics, Divisor is the number from which another number is divided, known as the dividend, to determine the quotient and remainder. In arithmetic, division is one of the four fundamental operations; other operations are addition, subtraction, and multiplication. In this article, we will disc

GCD (Greatest Common Divisor) Practice Problems for Competitive Programming

GCD (Greatest Common Divisor) or HCF (Highest Common Factor) of two numbers is the largest positive integer that divides both of the numbers. Fastest Way to Compute GCDThe fastest way to find the Greatest Common Divisor (GCD) of two numbers is by using the Euclidean algorithm. The Euclidean algorith

Euclid's Division Algorithm

The Euclidean Division Algorithm is a method used in mathematics to find the greatest common divisor (GCD) of two integers. It is based on Euclid's Division Lemma. In this algorithm, we repeatedly divide and find remainders until the remainder becomes zero. This process is fundamental in number theo

Extended Euclid Division Algorithm

The Extended Euclidean Algorithm is an extension of the classic Euclidean Algorithm. While the Euclidean Algorithm focuses on finding the greatest common divisor (GCD) of two integers, the Extended Euclidean Algorithm can also find integers x and y to express their greatest common divisor (gcd) as a

翻译：