Prime numbers

In this article we will be writing an algorithm to check if a provided number is a prime number or not. Before we begin let's define a few phrases that will be used during this article:

1. Factor: a number or quantity that when multiplied with another produces a given number or expression
2. A prime number: A whole number that only has two factors which are itself and one
3. A composite number: A whole number which is not prime

We can also state the following statements about primes and composites:

1. The numbers 0 and 1 are neither prime nor composite
2. All even numbers are divisible by two and so all even numbers greater than two are composite numbers
3. All numbers that end in five are divisible by five therefore all numbers that end with five and are greater than five are composite numbers

With that all said, let's start working on our tests and the implementation.

Tests

describe("prime number tests", () => {
  it('ignores negative numbers', () => {
    expect(isPrime(-1)).toBe(false);
  });

  it('ignores floating point numbers', () => {
    expect(isPrime(1.0001)).toBe(false);
  });

  it('ignores 0 and 1', () => {
    expect(isPrime(0)).toBe(false);
    expect(isPrime(1)).toBe(false);
  });

  it('identifies primes as expected', () => {
    const primes = [2, 3, 5, 7, 11, 13, 17, 19];
    for (const prime of primes) {
      expect(isPrime(prime)).toBe(true);
    }
  });

  it('identifies non-primes as expected', () => {
    const composites = [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20];
    for (const composite of composites) {
      expect(isPrime(composite)).toBe(false);
    }
  });
});

The tests here are quite simple but still covers our bases. We begin by testing that negative numbers, floating point numbers, 0 and 1 aren't prime. From there we test the numbers from 2 through 20 to check that the primes in that range come back as true and the composites come back as false. This makes sure we stick rigidly to the definition of what a prime number is and verify it by checking those numbers in the arbitrary range of 2 through 20.

Implementation

/**
 * @function isPrime
 * @description A function to identify if a given number is prime
 * @param {Number} number - The number to check
 * @returns {Boolean} represents if the provided number is prime or not
 */
function isPrime(number) {
  if(Number.isInteger(number) === false) return false;
  if(number <= 1) return false;
  if(number % 2 === 0 && number > 2) return false;

  const square = Math.sqrt(number);
  for (let divisor = 3; divisor <= square; divisor += 2) {
    if (number % divisor === 0) return false;
  }

  return true;
}

We begin the implementation of our isPrime function by filtering floating point numbers, numbers less than or equal to 1 and numbers divisible by 2 which are greater than 2 itself since 2 is prime. This helps us return false fast for items we know are not prime before running the inner loop and wasting any cycles.

From there we get the square root of the provided number. Lets illustrate the maths behind this to understand why we choose to do this.

If a number n is not a prime, it can be factored into two factors a and b.

n = a * b

If both a and b were greater than the square root of n then a times b would be greater than n. As such, at least one of those factors must be less than or equal to the square root of n. If we can't find any factors less than or equal to the square root, n must be prime.

Therefore we only need to loop up to the square root of the given number to check if the number is prime or not.

We start our loop at 3 since 2 is prime and will return true anyway due to the initial checks we run at the start of the function body. For each iteration of the loop we check if the provided number is fully divisible by the current divisor and if it is, we know the number cannot be prime since it must be a multiple of the divisor. In which case, we return false since a prime number should only be a multiple of itself and 1.

On each iteration we add 2 to the divisor as you may have noticed. This is because we know we aren’t dealing with an even number due to our previous checks and odd numbers aren’t divisible by even ones without a remainder being present and so we know we can skip checking even numbers during the iteration process. — thanks the @lukaszahradnik for the suggestion to do it like this

If no divisors between 3 and the square root of number were found then the number must be prime and so we return true.

Conclusions

There are many important real world use cases for prime numbers. Cicadas time their life cycles by them, modern screens use them for controlling the colour intensity of pixels and let's not forget the fact that they make up the very basis of computational security in implementations such as the RSA (Rivest–Shamir–Adleman) cryptosystem.

At the time of writing this article, the largest known prime to date is 2^82,589,933-1 (2 to the power of 82,589,933 minus 1). The resulting prime number is 24,862,048 digits long and that would make it approximately 2.5 times the length of the longest known book written to date in terms of digit count compared to character count using the average word length of 5 to determine the aforementioned character count.

Overall primes can be a fun topic to explore and have many important uses, there is even an organisation committed to finding more primes. I hope you learned something with this article and we will be exploring more mathematical constructs in the future and I hope to see you there!