A program that calculates the greatest common divisor and least common multiple of 2 numbers requested as input from the user.
The greatest common divisor (GCD) of two nonzero integers a and b is the greatest positive integer d such that d is a divisor of both a and b; that is, there are integers e and f such that a = de and b = df, and d is the largest such integer. The GCD of a and b is generally denoted gcd(a, b).
This definition also applies when one of a and b is zero. In this case, the GCD is the absolute value of the non zero integer: gcd(a, 0) = gcd(0, a) = |a|. This case is important as the terminating step of the Euclidean algorithm.
The above definition cannot be used for defining gcd(0, 0), since 0 × n = 0, and zero thus has no greatest divisor. However, zero is its own greatest divisor if greatest is understood in the context of the divisibility relation, so gcd(0, 0) is commonly defined as 0. This preserves the usual identities for GCD, and in particular Bézout's identity, namely that gcd(a, b) generates the same ideal as {a, b}. This convention is followed by many computer algebra systems. Nonetheless, some authors leave gcd(0, 0) undefined.
The GCD of a and b is their greatest positive common divisor in the preorder relation of divisibility. This means that the common divisors of a and b are exactly the divisors of their GCD. This is commonly proved by using either Euclid's lemma, the fundamental theorem of arithmetic, or the Euclidean algorithm. This is the meaning of "greatest" that is used for the generalizations of the concept of GCD.
The number 54 can be expressed as a product of two integers in several different ways:
Thus the complete list of divisors of 54 is:
Similarly, the divisors of 24 are:
The numbers that these two lists have in common are the common divisors of 54 and 24, that is:
Of these, the greatest is 6, so it is the greatest common divisor:
Computing all divisors of the two numbers in this way is usually not efficient, especially for large numbers that have many divisors.
In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, usually denoted by lcm(a, b), is the smallest positive integer that is divisible by both a and b.[1][2] Since division of integers by zero is undefined, this definition has meaning only if a and b are both different from zero.[3] However, some authors define lcm(a,0) as 0 for all a, since 0 is the only common multiple of a and 0.
The lcm is the "lowest common denominator" (lcd) that can be used before fractions can be added, subtracted or compared.
The least common multiple of more than two integers a, b, c, . . . , usually denoted by lcm(a, b, c, . . .), is also well defined: It is the smallest positive integer that is divisible by each of a, b, c, . . .
Multiples of 4 are:
Multiples of 6 are:
Common multiples of 4 and 6 are the numbers that are in both lists:
In this list, the smallest number is 12. Hence, the least common multiple is 12.
while (i<=n1 && i<=n2){
if (n1 %i ==0 && n2%i==0){
gcd=i;
}
i++;
}
while (k<=n1*n2){
if (k%n1==0 && k%n2==0){
lcm=k;
break;
}
k++;
}