4
\$\begingroup\$

I made my first ever JavaScript project. It is a program that calculates the GCD and LCM of 2 numbers that the user inputs. It also stores these 2 numbers in cookies so that they can be accessed for another 24 hours after being used. I made it so that the program calculates the prime numbers up to the larger number instead of using the Euclidean algorithm. I also couldn't find a goto equivalent in JavaScript so I couldn't make it so that the program won't check if i is prime over and over again. Some variables' names are in Turkish so they will be explained below. How could I improve my code? (I don't want to use the Euclidean algorithm, but I would like to find a way to skip checking if i is prime when it doesn't divide either number)

<!DOCTYPE html>
<html lang="en">
<head>
 <meta charset="UTF-8" />
 <meta name="viewport" content="width=device-width, initial-scale=1.0">
 <title>GCD LCM</title>
 <style>
 .no-spinners::-webkit-outer-spin-button,
 .no-spinners::-webkit-inner-spin-button {
 -webkit-appearance: none;
 }
 .no-spinners {
 -moz-appearance: textfield;
 }
 .form-row {
 display: flex;
 align-items: center;
 margin-bottom: 5px;
 }
 .form-row label {
 height: 25px;
 width: 110px;
 }
 #gonder {
 height: 30px;
 width: 100px;
 background-color: lightgreen;
 text-align: center;
 margin-top: 5px;
 margin-bottom: 5px;
 }
 </style>
</head>
<body>
 <form>
 <div class="form-row">
 <label for="number1">first number: </label>
 <input type="number" id="number1" name="number1" min="0" max="9999" class="no-spinners">
 </div>
 <div class="form-row"> 
 <label for="number2">second number:</label>
 <input type="number" id="number2" name="number2" min="0" max="9999" class="no-spinners">
 </div>
 <div class="form-row">
 <button type="button" id="gonder" onClick="CalculateGCDandLCM()">Calculate</button>
 </div>
 <div class="form-row">
 <label >GCD: </label>
 <label id="GCD"> </label>
 </div>
 <div class="form-row">
 <label>LCM: </label>
 <label id="LCM"> </label>
 </div>
 </form>
 <script>
 function getCookie(cname) { /*I took this function from the internet so I barely have any idea how it works */
 let name = cname + "=";
 let decodedCookie = decodeURIComponent(document.cookie);
 let ca = decodedCookie.split(';');
 for (let i = 0; i < ca.length; i++) {
 let c = ca[i];
 while (c.charAt(0) == ' ') {
 c = c.substring(1);
 }
 if (c.indexOf(name) == 0) {
 return c.substring(name.length, c.length);
 }
 }
 return "";
 }
 window.onload = function () {
 let number1cookie = getCookie("number1c"); /*cookies for the first and the second number*/
 if (number1cookie !== "") {
 document.getElementById("number1").value = parseInt(number1cookie, 10);
 }
 let number2cookie = getCookie("number2c");
 if (number2cookie !== "") {
 document.getElementById("number2").value = parseInt(number2cookie, 10);
 }
 };
 function CalculateGCDandLCM() {
 const d = new Date();
 d.setTime(d.getTime() + (24 * 60 * 60 * 1000));
 document.cookie = "number1c=" + document.getElementById("number1").value + "; expires=" + d.toUTCString() + "; path=/";
 document.cookie = "number2c=" + document.getElementById("number2").value + "; expires=" + d.toUTCString() + "; path=/";
 let isPrime = true, dividesFirstNumber = false, dividesSecondNumber = false;
 const primeDividers = []; /*this array stores prime numbers that divide both the first and the second number*/
 let indexer = 0;
 let firstNumber = parseInt(document.getElementById("number1").value, 10);
 let secondNumber = parseInt(document.getElementById("number2").value, 10);
 if (isNaN(firstNumber) || isNaN(secondNumber)) {
 alert("Please enter a real number");
 return;
 }
 /*store the initial values of the numbers*/
 let constBS = firstNumber;
 let constIS = secondNumber;
 let length = 0;
 if (firstNumber > secondNumber) { length = firstNumber; }
 else { length = secondNumber; }
 let i = 2;
 while (i < length) {
 if (i > 2) {
 for (let n = 2; n < i; n++) {
 if (i % n == 0) {
 isPrime = false;
 break;
 }
 }
 }
 if (isPrime) {
 if (firstNumber % i == 0) {
 firstNumber = firstNumber / i;
 dividesFirstNumber = true;
 }
 if (secondNumber % i == 0) {
 secondNumber = secondNumber / i;
 dividesSecondNumber = true;
 }
 if (dividesFirstNumber && dividesSecondNumber) {
 primeDividers[indexer] = i;
 indexer = indexer + 1;
 }
 }
 if (!dividesFirstNumber && !dividesSecondNumber) {
 i++;
 }
 isPrime = true; dividesFirstNumber = false; dividesSecondNumber = false;
 }
 let GCD = 1;
 for (let z = 0; z < indexer; z++) {
 GCD = GCD * primeDividers[z];
 }
 let LCM = (constBS * constIS) / GCD;
 document.getElementById('GCD').innerHTML = GCD;
 document.getElementById('LCM').innerHTML = LCM;
 }
 </script>
</body>
</html>
Ibram Reda
5662 silver badges10 bronze badges
asked Aug 29 at 16:37
\$\endgroup\$
1
  • \$\begingroup\$ Any reason to not use Euclidean algorithm? \$\endgroup\$ Commented Aug 30 at 3:20

3 Answers 3

6
\$\begingroup\$

I would like to find a way to skip checking if i is prime when it doesn't divide either number

Fortunately this is simple: you can just skip checking whether i is prime. Unconditionally.

If i = n * m such that 1 < n < i (so i is composite), then both n and m have been divided out of birinciSayi and ikinciSayi in earlier iterations. So a composite i doesn't pass the tests birinciSayi % i == 0 or ikinciSayi % i == 0 anyway, nothing happens in this iteration and we move on to the next i. Therefore, any i that passes the divisibility test has to be prime, all on its own, without needing the check that i is prime.

Furthermore, I've noticed a bug. If both birinciSayi and ikinciSayi are the same prime, this code gives 1 as their GCD, but of course the GCD of a number with itself is that number. So the condition i < length should perhaps be i <= length, or you can detect such situation after the loop (that may seem a little silly in this case, but you can use more efficient loop conditions that also rely on that extra step after the loop and then it makes sense to arrange it that way).

answered Aug 30 at 18:00
\$\endgroup\$
1
  • \$\begingroup\$ sorry for the late comment. thank you for your answer (I accepted and upvoted it.) I took your advice and made my program better. On top of that, I am using this to learn JavaScript better. I added some code to fetch the weather from weatherAPI. Cheers. \$\endgroup\$ Commented Sep 2 at 19:49
5
\$\begingroup\$

Javascript isn't my language at all, so I just have a small observation about this line at the end:

 let LCM = (constBS * constIS) / GCD;

We know that both numbers divide exactly by GCD so we can do the division first, reducing the likelihood of overflow:

 let LCM = constBS / GCD * constIS;

Even if JavaScript has transparent big-number support like Python, there's no need to go into slower big-num territory here.

answered Aug 31 at 7:11
\$\endgroup\$
1
  • 1
    \$\begingroup\$ JS does not (there are Number - 64-bit IEEE 754 float - and BigInt - infinite precision integer, but the latter can only be constructed manually, no automatic promotion exists), and you've touched a very important point: the function is just incorrect. Given enough time (probably a few days...), it will return the same (floating) LCM for (9007199254740991, 9007199254740992) and (9007199254740991, 9007199254740993). \$\endgroup\$ Commented Sep 2 at 15:08
1
\$\begingroup\$

I will only address the JS parts in this answer. Since this is your first JS post, I should forewarn: please do not take any code critique here personally. We write questions and answers here to improve our coding style and habits, and having them criticised really helps. What you have written is a good code for beginner, it is perfectly normal that your first attempts will need quite a bit of polishing.

Cookies?

Typically cookies are used for client-server communication. You have some (non-sensitive) data that is generated client-side and used client-side, localStorage is probably a better place for that.

Perf

Let's face it: this implementation is crawling slow. 200_000, 200_001 pair takes a few seconds to compute on my PC. That's really too slow.

Fortunately, you can apply the suggestion from another answer and skip the primality check, saving a lot of time. Also note that primality test does not need iteration up to n, Math.sqrt(n) should be enough.

And I believe that using established Euclidean algorithm will still be orders of magnitude faster.

Code organization

Now all the logic lives in a single function that's a bit too long and uses too many local variables. I'll avoid any logic changes in this section and will show how to make it more comprehensible, not necessarily more performant.

First of all, we want to be able to easily test the algorithm itself, without document, cookies or whatever else. Let's make this function pure: given two input numbers, return two numbers (GCD and LCM).

function gcdAndLcm(firstNumber, secondNumber) {
 ...
 return [gcd, lcm];
}
// XXX: JS functions are normally named in camelCase, not PascalCase
function CalculateGCDandLCM() {
 // read fields
 let a = ...;
 let b = ...;
 let [gcd, lcm] = gcdAndLcm(a, b);
 // store the result
 document.cookie = ...
}

Now let's do something with the main function.

The first obvious candidate is extracting isPrime to a separate function. This will save us a local variable and move a loop+if pair into its own helper - sounds helpful!

function isPrime(n) {
 for (let i = 2; i < n; i++) { // TODO: sqrt(n) would be a better limit
 if (n % i == 0) {
 return false;
 }
 }
 return true;
}

Now we can remove all occurrences of isPrime variable and rewrite the loop body as

 while (i < length) {
 if (!isPrime(i)) {
 continue;
 }
 if (firstNumber % i == 0) {
 firstNumber = firstNumber / i;
 dividesFirstNumber = true;
 }
 if (secondNumber % i == 0) {
 secondNumber = secondNumber / i;
 dividesSecondNumber = true;
 }
 if (dividesFirstNumber && dividesSecondNumber) {
 primeDividers[indexer] = i;
 indexer = indexer + 1;
 }
 if (!dividesFirstNumber && !dividesSecondNumber) {
 i++;
 }
 dividesFirstNumber = false; dividesSecondNumber = false;
 }

Now, we aren't writing old C, we're writing modern JS, right? Let's move the declarations to the right scope:

 let i = 2;
 while (i < length) {
 if (!isPrime(i)) {
 continue;
 }
 let dividesFirstNumber = false, dividesSecondNumber = false;
 if (firstNumber % i == 0) {
 firstNumber = firstNumber / i;
 dividesFirstNumber = true;
 }
 if (secondNumber % i == 0) {
 secondNumber = secondNumber / i;
 dividesSecondNumber = true;
 }
 if (dividesFirstNumber && dividesSecondNumber) {
 primeDividers[indexer] = i;
 indexer = indexer + 1;
 }
 if (!dividesFirstNumber && !dividesSecondNumber) {
 i++;
 }
 }

And maybe let's use the standard library:

// This
 let length = 0;
 if (firstNumber > secondNumber) { length = firstNumber; }
 else { length = secondNumber; }
// Can be spelled
 let length = Math.max(firstNumber, secondNumber)
// But what you really need is
 let length = Math.min(firstNumber, secondNumber)

(a number cannot have divisors greater than itself, so you know that gcd(7, 10**9+1) must be no more than 7, and checking all numbers up to 10**9 + 1 would be unnecessary - none of them can divide 7)

Let's look at what we have now:

function gcdAndLcm(firstNumber, secondNumber) {
 /*this array stores prime numbers that divide both the first and the second number*/
 const primeDividers = []; 
 let indexer = 0;
 let constBS = firstNumber;
 let constIS = secondNumber;
 let length = Math.min(firstNumber, secondNumber);
 let i = 2;
 while (i < length) {
 if (!isPrime(i)) {
 continue;
 }
 let dividesFirstNumber = false;
 if (firstNumber % i == 0) {
 firstNumber = firstNumber / i;
 // FIXME: should also recalculate length here,
 // no need to iterate past current minimum.
 dividesFirstNumber = true;
 }
 let dividesSecondNumber = false;
 if (secondNumber % i == 0) {
 secondNumber = secondNumber / i;
 // FIXME: should also recalculate length here,
 // no need to iterate past current minimum.
 dividesSecondNumber = true;
 }
 if (dividesFirstNumber && dividesSecondNumber) {
 primeDividers[indexer] = i;
 indexer = indexer + 1;
 }
 if (!dividesFirstNumber && !dividesSecondNumber) {
 i++;
 }
 }
 let GCD = 1;
 for (let z = 0; z < indexer; z++) {
 GCD = GCD * primeDividers[z];
 }
 let LCM = (constBS * constIS) / GCD;
 return [GCD, LCM];
}

Let's move one step further and notice that we do not need primeDividers and definitely do not need indexer. Adding a number to the array can be done using Array.prototype.push, and iteration does not need indexing (though there's also .length property if you need it).

const primeDividers = [];
while (...) {
 // ...
 primeDividers.push(i);
 // ...
}
let gcd = 1;
for (const d of primeDividers) {
 gcd *= d;
}
// or even
// const gcd = primeDividers.reduce((acc, d) => acc * d, 1);

but also... we only store them all to multiply everything together. Let's just keep track of the product:

function gcdAndLcm(firstNumber, secondNumber) {
 let gcd = 0;
 let constBS = firstNumber;
 let constIS = secondNumber;
 let length = Math.min(firstNumber, secondNumber);
 let i = 2;
 while (i < length) { // FIXME: Should be >=
 if (!isPrime(i)) {
 continue;
 }
 let dividesFirstNumber = false;
 if (firstNumber % i == 0) {
 firstNumber = firstNumber / i;
 // XXX: length = Math.min(firstNumber, secondNumber);
 dividesFirstNumber = true;
 }
 let dividesSecondNumber = false;
 if (secondNumber % i == 0) {
 secondNumber = secondNumber / i;
 // XXX: length = Math.min(firstNumber, secondNumber);
 dividesSecondNumber = true;
 }
 if (dividesFirstNumber && dividesSecondNumber) {
 gcd *= i;
 }
 if (!dividesFirstNumber && !dividesSecondNumber) {
 i++;
 }
 }
 const lcm = (constBS * constIS) / gcd;
 return [gcd, lcm];
}

Nice, huh? Let's shorten the conditions a bit:

 // XXX: triple-equals should be your default choice unless you
 // really need double-equals semantics
 const dividesFirstNumber = firstNumber % i === 0;
 const dividesSecondNumber = secondNumber % i === 0;
 if (dividesFirstNumber) {
 firstNumber = firstNumber / i;
 // XXX: length = Math.min(firstNumber, secondNumber);
 }
 if (dividesSecondNumber) {
 secondNumber = secondNumber / i;
 // XXX: length = Math.min(firstNumber, secondNumber);
 }
 if (dividesFirstNumber && dividesSecondNumber) {
 gcd *= i;
 } else if (!dividesFirstNumber && !dividesSecondNumber) {
 i++;
 }

Correctness / know your limits

JS numbers are not arbitrary-precision integers. For numbers big enough, your function will start returning wrong results whenever any intermediate number is not exactly representable as an IEEE 754 floating point number.

answered Sep 2 at 15:43
\$\endgroup\$
3
  • \$\begingroup\$ maybe programming isn't for me \$\endgroup\$ Commented Sep 2 at 19:52
  • \$\begingroup\$ @AnaKullanıcı of course not! We all need to learn, and this SE is a good place to learn more. \$\endgroup\$ Commented Sep 4 at 18:20
  • \$\begingroup\$ Thanks. I am trying... \$\endgroup\$ Commented Sep 4 at 22:46

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.