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.

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.
    1. Set every index hit to false because it is no longer a prime number.

Our code for this logic is as follows:

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 Java, JavaScript, Golang and a variety of frameworks such as Angular, NativeScript, and Apache Cordova. Nic writes about his development experiences related to making web and mobile development easier to understand.

  • maeglin79

    This is good like the other things you post. That’s why I have been following you for some months now. I just have a question. Is there a time when you would prefer using one method over the other in an interview situation if they do the same thing? Would employers prefer the shorter version over the longer one?

    • The Sieve of Eratosthenes algorithm will find all prime numbers up to a given limit, where as the other method I did will just check to see if the given number is prime. The Sieve of Eratosthenes algorithm is far more efficient to find prime numbers specially when it comes to larger values of N.

      I think it depends on what your employer is asking. If they ask you if a particular number is prime then the isPrime method should work fine since it has a time complexity of O(n). However if they ask you to find all numbers up to a given number, then I wouldn’t try to use that function because you’ll end up with a time complexity of O(n^2) because of nested loops.

      Employers are always going to look for efficient vs shorter / easy.

      Regards,

  • The brute force price checking is pretty slow. Learn how to profile and optimize javascript prime finding function in Angular web application http://glebbahmutov.com/blog/improving-angular-web-app-performance-example/ or in vanilla js https://github.com/bahmutov/vanilla-primes

  • Paul Verbeek
    • That looks pretty legit. I never thought to do it that way. RegEx is pretty awesome!

      Thanks for sharing!

    • G. James Carrow

      This looks cool. I’m not super familiar with regular expressions yet. So your method takes a number, turns it into an array of 1’s, and then what is it matching it against in the regular expression? Forgive my ignorance on the subject. I just found it interesting.

      • Paul Verbeek

        It’s a bit of a strange expression. If the regex is true, it is not a prime number.
        The first part (^1?$) checks if it’s a single 1, or an empty string. It returns true if that’s the case. So no prime number.
        The second part (^(11+?)1+$) is tricky. It matches even numbers, and if it’s not even it uses backtracking (with 1) to change the previously matched string to match a different string.

        You can see the full explanation on http://www.noulakaz.net/weblog/2007/03/18/a-regular-expression-to-check-for-prime-numbers/

        • G. James Carrow

          Right on!! Very cool. A cursory glance at it had me thinking it checked for odd or even, but I wasn’t seeing how it was going further and checking for prime. Really very cool. Thanks, man.

    • Agata

      if you add n>0 && that will be works when number is negative
      return n>0 && !(Array(n + 1).join(1).match(/^1?$|^(11+?)1+$/));

  • Qbe Root

    In the first function (i.e. the only one that really does what the title says), the loop doesn’t actually need to go up to the value you’re checking, not even value – 1. You can stop after Math.floor(Math.sqrt(value)), because each divisor of value greater than Math.sqrt(value) matches another divisor of value that is less than Math.sqrt(value). Example: in isPrime(30), you’ll never check 30 % 15 === 0 because 30 % 2 === 0 comes first and then the loop stops.

    • Thanks for sharing this information!

  • Your function won’t work with negative values and 0.

    I propose you this little update :

    function isPrime (nb) {
    for (var i = 2; i < nb/2; i++) {
    if (nb % i === 0)
    return false;

    }

  • Mike A (MikeTheWebDev)

    No, this is not a correct solution. Your javascript returns true for the value 1! 1 is not prime!

    • I think you’re correct. Instead of return true, I will change it to return value > 1.

  • Philippe Luchansky

    Nice write-up here!

    For efficiency’s sake, in your isPrime() function, it should also be noted that when iterating from 2 up to the value argument, you’ll never need to check for even divisibility past the halfway mark of ‘value’. In other words, if you pass 13 as the value argument, once the for loop’s ‘i’ iterator increments up past 13’s halfway mark, it would be redundant to continue checking for even divisibility, because if it reaches that halfway mark, it won’t be a prime. Here’s a variant of the for loop declaration with this edit:

    for(var i = 2; i < Math.floor(n / 2); i ++)

    It should yield the same results, but has the potential of being almost twice as efficient!

    • Thanks for sharing!

    • Everett

      You actually only need to iterate up to the rounded down square root of the number, for even more efficiency:

      for(var i = 2; i < Math.sqrt(Math.floor(n)); i++)

      • Jason Waters

        Actually, that doesn’t work. You have to change the loop to less than or equal to, like this:
        for (let i = 2; i <= parseInt(Math.sqrt(number)); i++) {

        Cheers

  • aynee

    can you please modify the code as “write a code that takes input from the use and checks wether it is prime or not?” can you write this code please??