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

Asked

Viewed 105 times

6

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>

  • I don’t know where you get it that they perform the same amount of iterations. There’s an exponential difference. One rotates almost a billion times and the other less than 30,000 times. Interestingly the second is less efficient in the case of not being cousin since it continues iterating even knowing the answer.

  • @bigown the amount of iterations is different, but the amount of loops is really equal. Each algorithm only has one for ;)

  • @Renan is true, I played loops as interactions :)

  • @Leocaracciolo troque isPrime = false; for return false;

  • @bigown predicted the comment of friend Renan :)rs

1 answer

8


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:

Função raiz

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.

  • 3

    I’d only get better still by putting one return in place of flag, not only pq is faster, but tb pq almost every time you have a flag there’s something wrong with the code, at least in style.

  • @Leocaracciolo boolean variables (those that receive the values true or false), when you use it to control script behavior.

Browser other questions tagged

You are not signed in. Login or sign up in order to post.