Javascript - Prime number function problem, memory overload

Question

I have the next problem. I am trying to find all the prime numbers until the specified number as input but when I am inputting for example really big numbers such as 13480000 or 643513511, the algorithm somehow stops to iterate and my browser is getting too slow in terms of processing the function. Here is the html code:

<!DOCTYPE html>
<html lang="es">
<head>
<script src="esPrimo.js">
</script>
</head>
<body>
<h1>Lista de primos</h1>
<form name="formu">
    <input id="txtValue" type="text" />
    <input type="button" value="Calcular!" onclick="proceso()">
</form>

<p id="res">El resultado se escribe aqui</p>
</body>
</html>

Here is my javascript code for the file of esPrimo.js

function proceso() {
    var value = document.querySelector('#txtValue').value;
    var primos = getPrimos(value);
    var output = document.querySelector('#res');
    output.innerHTML = primos.toString();

}

function getPrimos (value) {
    var primos = [];
    for (var i = 1; i <= value; i++){
        if (esPrimo(i)) primos.push(i);
    }
    return primos;
}

function esPrimo(n){
     if (isNaN(n) || !isFinite(n) || n%1 || n<2) return false; 
        var m = Math.sqrt(n);
        for (var i = 2; i <= m; i++)
            if (n % i == 0) return false;
        return true;
}

On the last function where the program is getting the parameter, gets very slow. It checks if n is dividible by every integer 2, 3, 4, 5 ... up to sqrt(n) but this version has the fewest lines of code. Moreover, I tried another way of iterating through all prime numbers like:

function esPrimo(n) {
if (isNaN(n) || !isFinite(n) || n%1 || n<2) return false; 
 if (n%2==0) return (n==2);
 var m=Math.sqrt(n);
 for (var i=3;i<=m;i+=2) {
  if (n%i==0) return false;
 }
 return true;
}

Here it checks the divisor 2 separately: then, it proceeds to check odd divisors only, from 3 up to sqrt(n). At most half of the numbers between 3 and sqrt(n) are checked.

How could I be able to optimize the code so that my program is able to calculate faster this kind of iterations ?

Any suggestions or advice, it would be really appreciating and helpful cause I have been trying to find somehow of a solution this past week, but it was of no use. Furthermore, I have one last link of interest in which I delved into and helped me quite a lot I would say in terms of grasping the primality test of numbers.

Javascript Primality Tests

Thanks

A smart Greek man, [Eratosthenes](https://en.wikipedia.org/wiki/Eratosthenes), figured out a much more efficient way to compute primes over 2000 years ago. — Pointy, Jan 31 '20 at 20:46
Well, yes it is quite useful but in any way I need to adapt it. Thanks! — Oris Sin, Jan 31 '20 at 22:06

score 3 · Accepted Answer · answered Jan 31 '20 at 21:40

Going off of what Pointy said in the comments, below is your JavaScript refactored to use Eratosthenes "sieve" algorithm. Before I get to the code, first a quick explanation of Erastosthenes. Erastosthenes found that you can more efficiently find prime numbers between 2 and N, where N is a large number, by finding the multiples of each number between the two and removing them from your list. Whatever you're left with must be prime.

E.G. N = 10

2, 3, 4, 5, 6, 7, 8, 9, 10 --> Multiples of 2 include 4, 6, 8 and 10, so they aren't prime. Multiples of 3 include 6 and 9, so they're removed. And so on. You're ultimately left with 2, 3, 5, 7, none of which had a number multiply into them.

Now, the code below uses Erastosthenes algorithm, but it will still break if you try your example of 643513511, I just think the processing power required by the browser is too much, but I could be wrong. It will, however, work for your example of 13 million.

Note: This code was refactored using your code and code taken from another Stackoverflow post, Sieve of Eratosthenes algorithm in JavaScript running endless for large number.

var getPrimos = function(n) {
    // Eratosthenes algorithm to find all primes under n
    var array = [], upperLimit = Math.sqrt(n), output = [];

    // Make an array from 2 to (n - 1)
    for (var i = 0; i < n; i++) {
        array.push(true);
    }

    // Remove multiples of primes starting from 2, 3, 5,...
    for (var i = 2; i <= upperLimit; i++) {
        if (array[i]) {
            for (var j = i * i; j < n; j += i) {
                array[j] = false;
            }
        }
    }

    // All array[i] set to true are primes
    for (var i = 2; i < n; i++) {
        if(array[i]) {
            output.push(i);
        }
    }

    return output;
};

Javascript - Prime number function problem, memory overload

1 Answers1