Why does one script freeze the browser and the other not if the number of loops is the same?

Question

I have 2 scripts To and B.

Testing whether a number is prime in the A script The browser freezes with large prime numbers - 9 digits - (e.g. ).

I tested in Chrome and IE, both browsers frozen.

In script B this same prime number does not freeze browsers, in fact it accepts numbers with more digits.

Script A freezes

function primo(num) {
    // verifica se o numero digitado é "1", que não é primo
    if(num!=1) {
        for (var i = 2; i < num; i++)
            if (num % i == 0) return false;
         return num !== 1;
    }
}

function verificaPrimo() {
    var num = document.getElementById("name").value;
    var resl="";
    // verifica se é número
    if(!isNaN(num)){
        // verifica se é primo
        if (primo(num)) {
           resl = "O número " + (num) + " é primo";
        } else {
            resl = "O número " + (num) + " nao éprimo";
        }
        document.getElementById("mensagem").innerHTML = resl;
    } else {
        document.getElementById("mensagem").innerHTML = "Vish, nem número é";
    }
}

<input type="text" id='name' />
<input type="button" name="botão" id="verificarvalor" value="Verificar" onclick="verificaPrimo()" />
<p id="mensagem"></p>

Script B

function primo() {
    var number = document.getElementById("number").value;
    if (!isNaN(number)) {
        if (isPrime(number)) {
            document.getElementById("mensagem").innerHTML = number + " É primo!";
        } else {
            document.getElementById("mensagem").innerHTML = number + " Não é primo.";
        }
    } else {
        document.getElementById("mensagem").innerHTML = "Só aceita números, volta pra escola";
    }
}

function isPrime(n) {
    if (n < 2) {return false}
        if (n != Math.round(n)) return false;
        var isPrime = true;
        for (var i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
    return isPrime;
}

<input id="number" value="0" maxlength="12" size="8" onclick="this.select()" />
<input type="button" value="Verificar" onclick="primo()" />
<p id="mensagem"> </p>

Answer 1

TL; DR: the browser "freezes" because it has many more calculations to do in the algorithm To.

It’s a matter of mathematics.

The two codes are similar. The main difference is in the number of iterations on the loops:

// A
for (var i = 2; i < num; i++)
    if (num % i == 0) return false;

and

// B
for (var i = 2; i <= Math.sqrt(n); i++) {
    if (n % i == 0) {
        isPrime = false
    }
}

By the way, this could be improved if you already hold the value of Math.sqrt(n) in a variable.

Math.sqrt(n) returns the square root of n. This means that for a certain number n, the algorithm loop To execute n times - but the algorithm loop B execute n^(1/2) times, rounded to the largest integer smaller than the root. The difference in the amount of runs is huge. See square root function curve:

In the event that n is equal to a thousand, the algorithm To runs a thousand times. Already the algorithm B runs only thirty times. The difference grows as n grows: to n equal to one million, the algorithm To runs a million times while B runs only a thousand times.

This works to find out if a number is prime, because every odd number that is not prime has a divisor smaller than its own square root. This decreases the amount of divisions you need to test to rule out a prime number.