From b3a6f3bc47098c81bef2c7d16690a5801149dbd8 Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Sun, 19 Aug 2018 15:28:15 -0500 Subject: Least Common Multiple done! Learned two interesting things: 1. Use GCD to get LCM https://www.idomaths.com/hcflcm.php#formula 2. To make a literal of numbers long, add L at the end of the number!--- AlgoDesignAndTechniqueEdxJava/sources/GCD.java | 24 ----------- AlgoDesignAndTechniqueEdxJava/sources/GcdLcm.java | 29 +++++++++++++ AlgoDesignAndTechniqueEdxJava/tests/GCDTest.java | 33 --------------- .../tests/GcdLcmTest.java | 48 ++++++++++++++++++++++ 4 files changed, 77 insertions(+), 57 deletions(-) delete mode 100644 AlgoDesignAndTechniqueEdxJava/sources/GCD.java create mode 100644 AlgoDesignAndTechniqueEdxJava/sources/GcdLcm.java delete mode 100644 AlgoDesignAndTechniqueEdxJava/tests/GCDTest.java create mode 100644 AlgoDesignAndTechniqueEdxJava/tests/GcdLcmTest.java diff --git a/AlgoDesignAndTechniqueEdxJava/sources/GCD.java b/AlgoDesignAndTechniqueEdxJava/sources/GCD.java deleted file mode 100644 index 5e29e4f..0000000 --- a/AlgoDesignAndTechniqueEdxJava/sources/GCD.java +++ /dev/null @@ -1,24 +0,0 @@ -import java.util.Scanner; - -public class GCD { - - public static int getGCD(int a, int b) { - if (b == 0) { - return a; - } - - if (b > a) { - return getGCD(b, a); - } else { - return getGCD(b, a % b); - } - } - - public static void main(String args[]) { - Scanner in = new Scanner(System.in); - int a = in.nextInt(); - int b = in.nextInt(); - - System.out.println(getGCD(a, b)); - } -} diff --git a/AlgoDesignAndTechniqueEdxJava/sources/GcdLcm.java b/AlgoDesignAndTechniqueEdxJava/sources/GcdLcm.java new file mode 100644 index 0000000..efef982 --- /dev/null +++ b/AlgoDesignAndTechniqueEdxJava/sources/GcdLcm.java @@ -0,0 +1,29 @@ +import java.util.Scanner; + +public class GcdLcm { + + public static int getGCD(int a, int b) { + if (b == 0) { + return a; + } + + if (b > a) { + return getGCD(b, a); + } else { + return getGCD(b, a % b); + } + } + + public static void main(String args[]) { + Scanner in = new Scanner(System.in); + int a = in.nextInt(); + int b = in.nextInt(); + + System.out.println(getLCM(a, b)); + } + + public static long getLCM(int a, int b) { + // https://www.idomaths.com/hcflcm.php#formula + return (long) a * (long) b / (long) getGCD(a, b); + } +} diff --git a/AlgoDesignAndTechniqueEdxJava/tests/GCDTest.java b/AlgoDesignAndTechniqueEdxJava/tests/GCDTest.java deleted file mode 100644 index 1c8fedd..0000000 --- a/AlgoDesignAndTechniqueEdxJava/tests/GCDTest.java +++ /dev/null @@ -1,33 +0,0 @@ -import static org.junit.jupiter.api.Assertions.*; -import org.junit.jupiter.api.Test; - -public class GCDTest { - @Test - void testGCD1() { - assertEquals(1, GCD.getGCD(18, 35)); - } - @Test - void testGCD2() { - assertEquals(17657, GCD.getGCD(28851538, 1183019)); - } - - @Test - void testGCD3() { - assertEquals(7, GCD.getGCD(1344, 217)); - } - - @Test - void testGCD4() { - assertEquals(1344, GCD.getGCD(1344, 1344)); - } - - @Test - void testGCD5() { - assertEquals(4, GCD.getGCD(14159572, 63967072)); - } - - @Test - void testGCD6() { - assertEquals(4, GCD.getGCD(63967072,14159572)); - } -} diff --git a/AlgoDesignAndTechniqueEdxJava/tests/GcdLcmTest.java b/AlgoDesignAndTechniqueEdxJava/tests/GcdLcmTest.java new file mode 100644 index 0000000..26806ce --- /dev/null +++ b/AlgoDesignAndTechniqueEdxJava/tests/GcdLcmTest.java @@ -0,0 +1,48 @@ +import static org.junit.jupiter.api.Assertions.*; +import org.junit.jupiter.api.Test; + +public class GcdLcmTest { + @Test + void testGCD1() { + assertEquals(1, GcdLcm.getGCD(18, 35)); + } + @Test + void testGCD2() { + assertEquals(17657, GcdLcm.getGCD(28851538, 1183019)); + } + + @Test + void testGCD3() { + assertEquals(7, GcdLcm.getGCD(1344, 217)); + } + + @Test + void testGCD4() { + assertEquals(1344, GcdLcm.getGCD(1344, 1344)); + } + + @Test + void testGCD5() { + assertEquals(4, GcdLcm.getGCD(14159572, 63967072)); + } + + @Test + void testGCD6() { + assertEquals(4, GcdLcm.getGCD(63967072,14159572)); + } + + @Test + void testLCM1() { + assertEquals(24, GcdLcm.getLCM(6,8)); + } + + @Test + void testLCM2() { + assertEquals(1933053046, GcdLcm.getLCM(28851538, 1183019)); + } + + @Test + void testLCM3() { + assertEquals(226436590403296L, GcdLcm.getLCM(14159572, 63967072)); + } +} -- cgit v1.2.3