Writing first 100 prime numbers to a file using node.js

Question

I am trying to teach myself node.js (no javascript or real programming experience) and have hit a road block on one of the problems I am trying to solve. My goal is to write the first 100 prime numbers to txt file. Below is my code so far.

var fs = require('fs');
var outfile = "test.txt";
var primality = function () {
    var arr = [];
    for (var n = 2; n <= 542; n++) {
        var primeTrue = true;
        for (var i = 2; i <= Math.sqrt(n); i++) {
            if (n % i === 0) {
                primeTrue = false;
            }
        }
        if (primeTrue) {
            arr.push(n);
        }
    }
    return arr;
}
fs.writeFileSync(outfile, arr);

I was using the codecademy javascript lab to test my loop and conditions and this code does seem to work. (It is also likely not the best way to do this since I had to set my counter to stop at 542 rather than have the program stop at the 100th prime number). In any event, when I added

var outfile = "test.txt"

and

fs.writeFileSync(outfile, arr);

this did not output the 100 prime numbers to the txt file as I thought it would. I'm still on the ground floor of my learning so I greatly appreciate any help you can provide.

Thank you in advance.

Kevin

Answer 1

You're doing a lot in one function. The code may be a bit easier to follow if you break it up into two functions, one to make the list of primes and another to test if a specific number is prime:

function listPrimes( nPrimes ) {
    var primes = [];
    for( var n = 2;  nPrimes > 0;  n++ ) {
        if( isPrime(n) ) {
            primes.push( n );
            --nPrimes;
        }
    }
    return primes;
}

function isPrime( n ) {
    var max = Math.sqrt(n);
    for( var i = 2;  i <= max;  i++ ) {
        if( n % i === 0 )
            return false;
    }
    return true;
}

Now you can run it in Node:

var fs = require('fs');
fs.writeFileSync( 'test.txt', listPrimes(100) );

or directly in the browser console:

listPrimes( 100 );

(I didn't test the code in Node, only in the browser.)

A couple of related notes:

1. The sqrt() calculation is moved outside the loop in isPrime(), so it doesn't have to be recalculated for each number you're testing.
2. The nPrimes variable lets you generate the exact number of primes you want without the 542 hack.

Having written this simple version, it's interesting to look at possible optimizations. One is to check for divisibility only on the previously generated primes, instead of checking all integers up to the square root. You could do that like this:

function listPrimes( nPrimes ) {
    var primes = [];
    for( var n = 2;  nPrimes > 0;  n++ ) {
        if( isPrime( n, primes ) ) {
            primes.push( n );
            --nPrimes;
        }
    }
    return primes;
}

function isPrime( n, primes ) {
    var max = Math.sqrt(n);
    for( var i = 0;  i < primes.length  &&  primes[i] <= max;  i++ ) {
        if( n % primes[i] === 0 )
            return false;
    }
    return true;
}

That may be faster if you're generating a large number of primes, although for 100 of them it hardly matters and I'd be inclined to stick with the simpler code.

Of course if you're talking about optimization, it's always worth considering a different algorithm. The Sieve of Eratosthenes is a fun one because it's fast and fairly simple and easy to understand. That Wikipedia article has a great illustration of how it works. In JavaScript it might look something like this:

function listPrimes( max ) {
    // Start with an empty list of primes
    var primes = [];
    // Initialize the sieve - each number is prime unless proven otherwise
    var sieve = new Array( max );
    for( var i = 1;  i <= max;  i++ ) {
        sieve[i] = true;
    }
    // Now check each number from 2 through max
    for( var p = 2;  p <= max;  p++ ) {
        if( sieve[p] ) {
            // p is prime, save it in the output list
            primes.push( p );
            // Mark p * 2, p * 3, p * 4, etc. as non-prime
            for( var t = p * 2;  t <= max;  t += p ) {
                sieve[t] = false;
            }
        }
    }
    return primes;
}

Yes, after recommending splitting the code into two functions, I'm now back to one function. :-)

One difference about the Sieve is that you can't really say, "please give me the first N primes"; instead you ask it, "please give me all the primes less than N". But if N is a large number, it is much faster than the other approach.

Answer 2

This works even beter if you preinitialize the list and skip testing the primality of multiples of 2

var primes = [2];
--nPrimes
for( var n = 3;  nPrimes > 0;  n += 2 )

I just finished very similar code for the Startup Engineering course homework @Coursera ;)