-
Notifications
You must be signed in to change notification settings - Fork 21k
Expand file tree
/
Copy pathGCD.java
More file actions
65 lines (59 loc) · 1.83 KB
/
GCD.java
File metadata and controls
65 lines (59 loc) · 1.83 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
package com.thealgorithms.maths;
/**
* This class provides methods to compute the Greatest Common Divisor (GCD) of two or more integers.
*
* The Greatest Common Divisor (GCD) of two or more integers is the largest positive integer that divides each of the integers without leaving a remainder.
*
* The GCD can be computed using the Euclidean algorithm, which is based on the principle that the GCD of two numbers also divides their difference.
*
* For more information, refer to the
* <a href="https://en.wikipedia.org/wiki/Greatest_common_divisor">Greatest Common Divisor</a> Wikipedia page.
*
* <b>Example usage:</b>
* <pre>
* int result1 = GCD.gcd(48, 18);
* System.out.println("GCD of 48 and 18: " + result1); // Output: 6
*
* int result2 = GCD.gcd(48, 18, 30);
* System.out.println("GCD of 48, 18, and 30: " + result2); // Output: 6
* </pre>
* @author Oskar Enmalm 3/10/17
*/
public final class GCD {
private GCD() {
}
/**
* get the greatest common divisor
*
* @param num1 the first number
* @param num2 the second number
* @return gcd
*/
public static int gcd(int num1, int num2) {
if (num1 < 0 || num2 < 0) {
throw new ArithmeticException();
}
if (num1 == 0 || num2 == 0) {
return Math.abs(num1 - num2);
}
while (num1 % num2 != 0) {
int remainder = num1 % num2;
num1 = num2;
num2 = remainder;
}
return num2;
}
/**
* @brief computes gcd of an array of numbers
*
* @param numbers the input array
* @return gcd of all of the numbers in the input array
*/
public static int gcd(int... numbers) {
int result = 0;
for (final var number : numbers) {
result = gcd(result, number);
}
return result;
}
}