Stuck with Javascript array , node

Question

Stuck with Javascript array , node

I am very new at javascript/node and I am stuck at a question in which I have to find prime numbers. I think my logic is correct but it is producing extra numbers. Here is code For now I am using array from 2 to 100. Thank you In advance

var num = [2];
for (var i = 3; i < 101; i++){
  num.push(i);
}

for(i = 0; i <= num.length; i++){
  for(var k = 2; k <= i; k++){
    if( (num[i] % k) == 0){
      num.splice(i, 1);
    }
  }
}

var fs = require('fs');
var outfile = "hel.txt";
fs.writeFileSync(outfile, num);

javascript
arrays
node.js

Answer 1

The satement "but it is producing extra numbers" is not quite correct. You produced the array containing all numbers up to 100 at the beginning. The problem is that not all non-prime numbers are removed.

Why? Because you are modifying the array while you are iterating over it. The consequence is that some entries won't be checked, they will be skipped.

Example:

Imagine the array

var num = [2,3,4,5,6,7,8,9,10,11];

Let i be 7, so we are testing num[7] = 9. 9 is not prime so it is removed from the array, which then looks like

var num = [2,3,4,5,6,7,8,10,11];

In the next iteration i is 8 and we are testing num[8] = 11. Notice how 10 was not tested? Originally 10 was at index 8 but since we removed 9, its new index is 7, which we already tested. The size of the array changed and all elements "to right of" 9 have been moved one position to the left.

To solve this, you can iterate over the array in reverse order (I also think k <= i should be k < num[i]):

for (i = num.length - 1; i > -1; i--) {
  var n = num[i];
  for (var k = 2; k < n; k++) {
    if ((n % k) == 0) {
      num.splice(i, 1);
      break; // you can stop testing after you found a factor
    }
  }
}

Small suggestion to your algorithm: It is enough to only test factors up to the square root of the number, i.e.:

for (var k = 2, r = Math.sqrt(n); k <= r; k++) {
    if ((n % k) == 0) {
      num.splice(i, 1);
      break;
    }
}

There are probably other possible improvements as well, have a look at http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.

Answer 2

Try this:

 for(i = num.length; i >= 0; i--){
    findFactors: for(var k =2; k <= i; k++){
        if(num[i]%k ==0){
             num.splice(i,1);
             break findFactors;
        }
    }

I haven't tested it so not sure if it works...