Javascript Avoiding Nested For Loops

Question

I've noticed my algorithm solutions often include ugly nested for loops when better options are available. In the example below, how can I determine the prime numbers up to the given parameter without nested loops? One constraint of the assignment was to not utilize any external functions.

function sumPrimes(num) {
    var p = [];
    for (var i = 2; i <= num; i++)
    {
        p.push(i);
        for (var j = 2; j < i; j++)
        {
            if (i % j === 0) //not a prime
            {
                p.pop(i);
                break;
            }
        }
    }
    return p;

Just about anywhere you use nested loops, you can use recursion. It is typically a more complicated solution to wrap your mind around, but they accomplish the same task — mhodges, Mar 30 '17 at 22:49
What do they mean by "external" functions? You can move the inner loop to its own function but define it inside `sumPrimes`. Or are they saying not to use library functions? — , Mar 30 '17 at 22:54

score 0 · Answer 1 · edited May 23 '17 at 12:17

I don't know if there is any other good solution but I came up with this. There is still one for loop ;)

function primes(num) {
  return Array.apply(null, {length: (num + 1)}).map(Number.call, Number)
   .filter(function(n) {
     for(var i = 2; i < n; i++) {
       if(n % i === 0) return false;
     }
     return n !== 0 && n !== 1;
   })
 }

Explanation:

Array.apply(null, {length: (num + 1)}).map(Number.call, Number)

This line creates an Array with the range of the passed argument. If num would be 5 it would create the following Array: [0, 1, 2, 3, 4, 5]. I found this here.

Then I use the filter function to remove all non prime numbers. If the filter function returns false the number will be removed from the array. So inside the filter function we check if the current number is a prime number. If so, true is returned. As you can see I still use a normal for loop here.

No you can call the function as follows: primes(28);

This will return the following Array: [ 2, 3, 5, 7, 11, 13, 17, 19, 23 ]

In this specific case I would say to use normal for loops is absolutely ok. But always consider functions like map, reduce or filter when you operate on arrays.

This answer is not exactly correct, `.map()` & `.filter()` are for loops but disguised on a built-in javascript method. — Juan Burolleau, Jan 27 '22 at 08:22

Javascript Avoiding Nested For Loops

1 Answers1