Using JavaScript to Find Prime Numbers

There’s a relatively common interview question that asks you to write a chunk of JavaScript to find prime numbers. I thought I’d tackle it without the pressure of someone watching over my shoulder. To that end, I built getPrimes.js to do the work for me.

 What’s Going On

The basic concept here (and what interviewers are going for) is to build nested loops. First, you iterate through your list of numbers to check, then for each one we check what that number is divisible by (using the modulus operator %).

It can take some serious resources, especially when you get into larger numbers. To give you an idea, it takes supercomputers months to find the next biggest prime number (which is currently a number with 22,338,618 digits).

Admittedly, getPrimes has some extra features in it that you may wish to prune out. These include: logging, duration of calculation, and finding the biggest and smallest prime in the set.

Have fun and happy coding.

Get it on GitHub

The Code

function getPrimes(min, max, log) {
    //Default logging to off.  
    if (typeof log === "undefined") {
        var log = false;
    }
    //Can't do primes under 1.
    if (min < 1) {
        min = 1;
        if (log) {
            console.warn("Starting number was less than 1, using 1 instead.");
        }
    }
    //Get rid of any decimals.
    min = Math.floor(min);
    max = Math.floor(max);
    var start = new Date(); //Get a timestamp of when we started.
    var foundLowest = false;
    var primeArray = []; //Initialize the output array.
    if (min <= max) {
        for (var i = min; i <= max; i++) {
            if (log) {
                console.log("Checking: " + i);
            }
            var divCount = 0;
            for (var t = 1; t <= i; t++) {
                if (i % t === 0) {
                    divCount++;
                }
            }
            if (divCount <= 2) {
                //It's a Prime! Grab it.
                primeArray.push(i);
                primeArray.highest = i;
                if (!foundLowest) {
                    primeArray.lowest = i;
                    foundLowest = true;
                }
            }
        } //End main loop.
    } else {
        primeArray.lowest = 0;
        primeArray.highest = 0;
        if (log) {
            console.error("Error: Starting value is larger than ending value. An empty array will be returned.");
        }
    }
    //End if min <= max.
    var end = new Date(); //Timestamp when we finished.        
    primeArray.duration = (end - start); //Total computation time.
    if (log) {
        console.log("Computation took " + primeArray.duration + "ms");
    }
    return primeArray;
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.