Finding Primes

Finding prime numbers is a relatively straightforward algorithm to code and one which might reveal some interesting coding behaviors. It requires a little - but not much - mathematical knowledge and can be implemented in just about any language.

In case you don't know, a prime number is any number that is only divisible by 1 and itself.

Problem Statement

Given a number N, find all prime numbers from 1 to N.

The first thing you should do if given this question is to clarify it. Here are some example questions you could ask from this statement:

• Should you also check N? Or just numbers less than N?
• Do you consider 1 and 2 to be prime? (Not all mathematicians do ...)
• Do you want them output or stored?

Even after you start coding, if you find that you're not sure what they're expecting ask the interviewer for clarification.

Pseudocode

Before you start coding you should always write your algorithm down as pseudocode. This will help you organize your thoughts and to make sure that you've asked all the clarifying questions you need to ask.

• Iterate through all numbers from 1 to N as I
  • Assume I is prime
  • Iterate through all numbers from 1 to I as J
    • If I is divisible by J, it's not prime
  • If I was not divisible by any J, add to list of primes

Now that you have a rough sketch of how you plan to solve this question, you can start coding

Initial Code

First we're going to start with a simple function outline, defining some variables, and our main loop. The following code is in JavaScript.

function findPrimes(n) {
    var primeList = new Array();
    var i, j;

    // check all the numbers up to n (parameter)
    for (i=1;i<n;i++) {

    }
}

Here we need the clarifying questions we asked earlier. Let's write this code assuming that the interviewers told you:

• 1 and 2 don't count as primes.
• You should also check N.

And, since we're coding to impress, let's add a comment to describe the function. (And since we really want to impress, I'm going to use the standardized JS Doc format.)

If you can't remember the specifics for JS Doc during an interview - don't panic. Just remember:

• describe what the function does
• describe what the parameters are
• describe what the function returns

If you write that information in plain text, that'll probably still impress most interviewers.

/**
 * Finds all prime numbers between 1 and N inclusive. 1 and 2 don't count.
 * @param {Number} n the highest number we should check
 * @returns {Array} list of prime numbers
 */
function findPrimes(n) {
    var primeList = new Array();
    var i, j;

    // check all the numbers from 3 to N
    for (i=3;i<=n;i++) {

    }
}

Okay, now we're ready to code that inner loop - the one that will check if i is prime. The inner loop check through all the numbers less than i and sees if i is divisible by any of those numbers. If the number is prime, we add it to our list.

/**
 * Finds all prime numbers between 1 and N inclusive. 1 and 2 don't count.
 * @param {Number} n the highest number we should check
 * @returns {Array} list of prime numbers
 */
function findPrimes(n) {
    var primeList = new Array();
    var i, j;
    var isPrime;

    // check all the numbers from 3 to N
    for (i=3;i<=n;i++) {
        // assume the number is prime
        isPrime = true;

        // iterate through possible divisors
        for (j=2;j<i;j++ ) {
            // if divisible by this number, mark as NOT prime
            if (i % j == 0) {
                isPrime = false;
                // end the inner loop since we have a definitive answer
                j = i;
            }
        }
    }
}

Now that we know which numbers are prime, we need to put them into the list and, finally, return that list at the end of the function.

/**
 * Finds all prime numbers between 1 and N inclusive. 1 and 2 don't count.
 * @param {Number} n the highest number we should check
 * @returns {Array} list of prime numbers
 */
function findPrimes(n) {
    var primeList = new Array();
    var i, j;
    var isPrime;

    // check all the numbers from 3 to N
    for (i=3;i<=n;i++) {
        // assume the number is prime
        isPrime = true;

        // iterate through possible divisors
        for (j=2;j<i;j++ ) {
            // if divisible by this number, mark as NOT prime
            if (i % j == 0) {
                isPrime = false;
                // end the inner loop since we have a definitive answer
                j = i;
            }
        }

        // if the number is prime, add it to the list
        if (isPrime) primeList.push(i);
    }

    return primeList;
}

Congratulations, you've officially solved the problem! But now let's improve on our answer.

Improvements and Optimizations

JavaScript is a wonderful language for writing code quickly, but it has one glaring weakness: it's loosely typed. We need our input number n to be a positive integer or else we're in for unexpected results.

The first and most important improvement to add is an error check. Fast code is good - but stable code is best. Since we're checking for an error, we also need to update our code to report an error.

/**
 * Finds all prime numbers between 1 and N inclusive. 1 and 2 don't count.
 * @param {Number} n the highest number we should check
 * @returns {(Array|Boolean)} list of prime numbers, or false on bad input
 */
function findPrimes(n) {
    var primeList = new Array();
    var i, j;
    var isPrime;

    if (typeof(n)!="number" || n<0) {
        return false;
    }

    // check all the numbers from 3 to N
    for (i=3;i<=n;i++) {
        // assume the number is prime
        isPrime = true;

        // iterate through possible divisors
        for (j=2;j<i;j++ ) {
            // if divisible by this number, mark as NOT prime
            if (i % j == 0) {
                isPrime = false;
                // end the inner loop since we have a definitive answer
                j = i;
            }
        }

        // if the number is prime, add it to the list
        if (isPrime) primeList.push(i);
    }

    return primeList;
}

Now we should turn our eye toward speed. We can use what we know about prime numbers to cut down on the number of checks we do. We're going to start i at 3, but we're going to increment by 2 so that we can skip all even numbers (since every even number is divisible by 2).

We can also start checking for factors at 3 instead of 2 since we're guaranteed no even numbers.

/**
 * Finds all prime numbers between 1 and N inclusive. 1 and 2 don't count.
 * @param {Number} n the highest number we should check
 * @returns {(Array|Boolean)} list of prime numbers, or false on bad input
 */
function findPrimes(n) {
    var primeList = new Array();
    var i, j;
    var isPrime;

    if (typeof(n)!="number" || n<0) {
        return false;
    }

    // check all the ODD numbers from 3 to N
    for (i=3;i<=n;i+=2) {
        // assume the number is prime
        isPrime = true;

        // iterate through possible divisors
        for (j=3; j<i; j++ ) {
            // if divisible by this number, mark as NOT prime
            if (i % j == 0) {
                isPrime = false;
                // end the inner loop since we have a definitive answer
                j = i;
            }
        }

        // if the number is prime, add it to the list
        if (isPrime) primeList.push(i);
    }

    return primeList;
}

The last optimization we're going to add has a large performance impact but it requires one insight about factors: every factor for a number has a pair. For example, 15 is divisible by 1 and 15, but also 3 and 5 - and you know they come in a pair because they have to be multiplied together to get 15.

The only time a factor doesn't have a pair is if the factor is the square root of the number. For example, 9 is divisible by 1 and 9, but also 3 - since 9 is 3².

And now the mathematical fact that will actually help us out here: For any factor that has a pair, one factor will be below the square root of the number, and the other factor will be above the square root of the number. This means that we only have to check up to and including the square root of i because if there were a factor greater than the square root we would've already found its pair below the square root.

/**
 * Finds all prime numbers between 1 and N inclusive. 1 and 2 don't count.
 * @param {Number} n the highest number we should check
 * @returns {(Array|Boolean)} list of prime numbers, or false on bad input
 */
function findPrimes(n) {
    var primeList = new Array();
    var i, j;
    var isPrime;

    if (typeof(n)!="number" || n<0) {
        return false;
    }

    // check all the ODD numbers from 3 to N
    for (i=3;i<=n;i+=2) {
        // assume the number is prime
        isPrime = true;

        // find our limiter
        var limiter = Math.sqrt(i);
        // iterate through possible divisors
        for (j=3; j<=limiter; j++ ) {
            // if divisible by this number, mark as NOT prime
            if (i % j == 0) {
                isPrime = false;
                // end the inner loop since we have a definitive answer
                j = i;
            }
        }

        // if the number is prime, add it to the list
        if (isPrime) primeList.push(i);
    }

    return primeList;
}

And that's it - a pretty solid answer to this question. If you have any questions don't hesitate to contact me (contact info is on the homepage). Also let me know if you spot any typos, or if there's an interview question you'd like me to tackle.