Determine If A Number Is Prime Using JavaScript

Continuing on the topic of interview questions for programming and software engineering type positions, I thought I’d brush up on a popular one.

Although I have never personally been asked about this, other people have told me that they’ve been asked to determine if a number is prime or to print out all prime numbers up to a certain number.

This is not too difficult a problem as long as we understand what a prime number is. So what makes a number a prime number? A prime number via Wikipedia is as follows:

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

With that said, let’s think of a few possible ways to approach this problem.

In most programming languages there is a modulus type function for determining the remainder of a division between two numbers. We can certainly use this concept for determining if a number is prime because a modulus expression will return zero if the number isn’t prime.

function isPrime(value) {
    for(var i = 2; i < value; i++) {
        if(value % i === 0) {
            return false;
        }
    }
    return value > 1;
}

In the above code we accept a number to determine whether or not it is prime. We then loop from two all the way up until our number minus one because we know that our number will be divisible by itself and one. If the remainder of our value with the current loop value is zero then we know it is not prime so break out and say so.

Now I also read on the internet you can make use of what is called the Sieve of Eratosthenes algorithm to accomplish this problem.

Sieve of Eratosthenes via Wikipedia:

A simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the multiples of 2.

The logic behind what we’re about to do is as follows:

1. Create an array from two until the value and assign a value of true since we are going to assume everything is prime to start.
2. Take the square root of our desired value which will represent a limit to our looping.
3. Loop from two until our new square rooted limit.
4. Check to see if our current index is prime, otherwise ignore it.
5. Loop through (i * i) + ix until our initial value where x is incremental starting from value one.
6. Set every index hit to false because it is no longer a prime number.

Our code for this logic is as follows:

function printPrime(value) {
    var primes = [];
    for(var i = 2; i < value; i++) {
        primes[i] = true;
    }
    var limit = Math.sqrt(value);
    for(var i = 2; i < limit; i++) {
        if(primes[i] === true) {
            for(var j = i * i; j < value; j += i) {
                primes[j] = false;
            }
        }
    }
    for(var i = 2; i < value; i++) {
        if(primes[i] === true) {
            console.log(i + " " + primes[i]);
        }
    }
}

The above code will also print all the prime numbers up until the limit when it is complete.

Conclusion

Determining if a number is prime or printing all prime numbers up to a limit is a common interview question. There are numerous methods for accomplishing this and I’ve listed two. If you think you have a better way to solve this problem or have been asked a question similar to this in an interview, please share your experiences in the comments as they may help potential job seekers.

Nic Raboy

Nic Raboy is an advocate of modern web and mobile development technologies. He has experience in C#, JavaScript, Golang and a variety of frameworks such as Angular, NativeScript, and Unity. Nic writes about his development experiences related to making web and mobile development easier to understand.