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

Question

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

Navigation

#1 by (9 votes)

6

I have 2 scripts A and B .

Testing if a number is prime in script A, the browser freezes with large prime numbers - 9 digits - (eg 777767777).

I tested Chrome and IE, both browsers froze.

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>

javascript

asked by anonymous 14.04.2017 / 13:32

1 answer

How to set the equality comparison between two objects present in an ArrayList? Filter in DropDown using C # MVC 4

score 9 · Accepted Answer

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

It's a matter of math.

The two codes are similar. The main difference is in the number of iterations in 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 have already stored the value of Math.sqrt(n) in a variable.

Math.sqrt(n) returns the square root of n . This means that, for a given number n , the loop of the A algorithm will execute% as_% of times - but the loop of the B algorithm will execute n times, rounded to the largest integer smaller than the root. The difference in the number of executions is enormous. See the square root function curve:

In the case where n^(1/2) equals a thousand, the algorithm A runs a thousand times. Already the B algorithm runs only thirty times. The difference grows as n grows: for n equal to one million, algorithm A 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 the assumption that a number is prime.