Finding prime numbers

I’ll follow the usual process of my problem solving in this post. I’ll start with the problem statement followed by some maths (just for fun), and then I’ll dissect the problem to show how I would solve it and finally comes the solution.

As always, if you don’t feel the urge, you are free to skip the maths section.

Problem statement

Today’s challenge: Find all primes up to 100 and list them as a comma-separated string.

Maths background

Let’s start with the definition. We say that a positive integer (whole number) is a prime number if it has exactly two divisors (no more, no less), namely 1 and itself. This means that 1 is not a prime as it has only one divisor.

For example, 3 is a prime because both 1 and 3 go evenly into 3, but 4 is not a prime but a composite number because not only 1 and 4 go into it but 2 as well, so it has 3 divisors.

You might remember from high school that one way to find primes is to use the sieve of Eratosthenes.

Eratosthenes was a Greek scientist, which by itself is a problem because it adds another item to the school curriculum, but he will help us a lot here with the method he invented.

As for the method, we take each whole number starting from 2. If the given number is already a multiple of another (obviously smaller) number, we ignore it. If not, we circle it, because it’s a prime.

For example, 2 is a prime, so we circle it and cross out all of its multiples (4, 6, 8, etc. up to 100). Then we move on to 3. It’salso a prime, so circle it, and cross out all multiples of 3 (6, 9, 12, … , 99). Next number is 4, but it’s a multiple of 2 and is already crossed out, so we have nothing to do with it. We can move on to the next number, 5, and go over the same procedure and so on and on. Doing this up to 100 we can find all primes.

This works well with a pen and paper but as you can guess, the method can be time consuming if we are asked to find all primes, say up to 10000. However, the sieve of Eratosthenes will be the base of our solution below.

This concludes the maths lesson for today, I hope you enjoyed it and we can now move on to the coding part and create an algorithm.

Breaking it down

As always, we start by dissecting the problem into small pieces and then we will call the definition of primes and the sieve of Eratosthenes for help.

We take each number and investigate if it’s a multiple of another number. It would be great if we had a collection of composite numbers (which are the multiples of primes) and check if the given number can be found in the collection.

If the number we are checking is in the collection, we can ignore it, because it cannot be a prime.

If the given number is not in the collection, it will definitely be a prime, so we need to mark the number as a prime. It would also be great if we could calculate all of its multiples and store them in the composite collection.

We also need to consider a threshold number (100 in this case) up to which we need to mark and list the primes.

JavaScript methods used

The blueprint is given; it’s time to translate all of the above into JavaScript.

First, we will need a collection of composite numbers. One might think of an array at first but the problem is that we will have common multiples as we move on to bigger numbers. For example, 15 is the multiple of both 3 and 5, so the array would contain 15 twice, once when we list the multiples of 3 and once when we get the multiples of 5. This is not necessary a problem here but provides an unnecessary redundancy.

I personally think a nicer solution for the composite collection would be a set. A given element can only occur once in a set, so we won’t be able to add it to the collection for the second time.

We will also need a collection of primes, which can be an array because there won’t be any duplication of values in this collection.

We will iterate over the positive whole numbers starting from 2, so a for loop can be a good solution. A second iteration will also be needed for checking the multiples collection.

Lastly, we will need to join the values of the primes’ collection, separate each number with a comma and have to return it.

Solution

You can find the list of all primes below 10000 here, so this site will come handy when we want to check our solution. By looking at the list of prime numbers, we know that our result string must start with 2 and must end with 97.

The function that returns the primes received the expressive name of getPrimes. This function will accept one parameter and this will be the threshold number (100 in our case), which the primes should be less than or equal to:

function getPrimes(threshold) {
  const primes = [];
  const composites = new Set();
}

getPrimes(100);

We created the primes array and the composites set as well, both are initially empty.

We can now move on to the exciting part and start iterating over the integers greater than or equal to 2 and go up to 100:

for (let i = 2; i <= threshold; i++) {
  if (composites.has(i)) continue;

  primes.push(i);

  for (let j = 2; j * i <= threshold; j++) {
    composites.add(j * i);
  }
}

The expressions in the first for statement are straightforward: we go from 2 to the threshold number. We then check if the current number in the iteration (i) is included in the composites set. The has method of the Set object can be used to determine if a given value is included in the set. If so, jump on to the next number in the iteration with continue. When continue is used, the rest of the statements inside the curly braces won’t run but the value of i will be increased by 1 and for starts the process over by checking again if it’s included in the composites collection.

What if the current i is not included in composites? Then we have found a prime! Instead of circling it, we push that number into the primes array and virtually cross out all of its multiples.

How?

We do this operation by using another for loop and calculate the composite numbers.

How can we find all the multiples of a number?

We take the number and multiply it by all integers starting from 1. For example, the multiples of 2 are 2 * 1 = 2, 2 * 2 = 4, 2 * 3 = 6, etc. Again, we take the whole numbers in italic and iterate over them, so we can use a for statement here.

But in the second loop j will also start from 2 and not 1. Why? Because multiplying a number by 1 gives the number itself, and we have already marked that number as a prime and have pushed it into primes. Composite numbers can be found by multiplying the number by at least 2.

The condition of the second for statement is that the multiples (j * i) should be less than or equal to the threshold number, which is 100 in this case. Once we have the multiples (j * i), we add them to the composite set. The add method, as its name suggests, adds a value to the set.

Now that the hard part (which was not so hard, was it?) is done, oen thing left and this is to create a comma-separated list from the array of primes. We can do this by using the join method, which is available on the Array object. The parameter of join is a string which refers to the separator of the items. The default separator is the ,, so we can simply leave it out and use join with no parameter:

function getPrimes(threshold) {
  const primes = [];
  const composites = new Set();

  for (let i = 2; i <= threshold; i++) {
    if (composites.has(i)) continue;

    primes.push(i);

    for (let j = 2; j * i <= threshold; j++) {
      composites.add(j * i);
    }
  }

  return primes.join();
}

Let’s call the function:

getPrimes(100);
// returns 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

This way we made the function configurable, so you can easily find all primes up to a certain number. You can also check the result on the website referred above.

Considerations

We haven’t discussed any edge cases yet. What if we call the function with a value of other than number type? What if we invoke it with a negative number or a non-integer?

Entering a positive non-integer won’t affect the result. For example, when calling getPrimes with 99.7, the function will give the same correct result.

In case of negative numbers or non-numbers though, the function will return nothing, so it might make sense to write a lines of code to notify the user:

if (typeof threshold !== 'number' || threshold < 0) return 'Please enter a positive integer.';

Also, if we enter a number that is less than 2, there won’t be any primes found, so let’s handle this case as well:

if (threshold < 2) return 'No primes found.';

So the final code can look like this:

function getPrimes(threshold) {
  if (typeof threshold !== 'number' || threshold < 0) return 'Please enter a positive integer.';
  if (threshold < 2) return 'No primes found.';

  const primes = [];
  const composites = new Set();

  for (let i = 2; i <= threshold; i++) {
    if (composites.has(i)) continue;

    primes.push(i);

    for (let j = 2; j * i <= threshold; j++) {
      composites.add(j * i);
    }
  }

  return primes.join();
}

Conclusion

Finding and listing primes is a nice little problem. As always, I have to mention that the above solution is definitely not the only one. It is a working solution, so if you know something else, feel free to share it with me on Twitter. See you next time!