Three exercises with primes numbers

We call a number a prime if it has exactly two factors: 1 and itself. So 1 is not a prime number because it only has one factor (1). Easy.

Some mathematical background

Primes are great and many smart mathematicians devoted their life to research their behaviour. It’s believed that Euclid was the first to prove that infinitely many primes exist (the link contains an easy mathematical proof, so think twice before you click on it). A Hungarian mathematician, Paul Erdos, was famous of having no place of residence (he travelled the world in his whole life living from a piece of luggage) and of his love for prime numbers.

Primes are great and special! The functions coming below are all about primes and solve various prime-related problems. They will require some mathematics and if the reader is not a big fan of one of the most beautiful sciences in the world (this would be mathematics), I will provide an explanation and try to shed light on these concepts.

As always, these solutions are not the only correct ones and feel free to come up with other algorithms.

Check if a number is a prime

First we might want to know if a number we randomly choose is a prime.

Our function is called isPrime and returns true if the number passed as an argument is a prime and false if it’s not. isPrime can look like this:

function isPrime(num) {
  if (!Number.isInteger(num)) return false;

  if (num <= 1) return false;
  if (num === 2) return true;

  if (num % 2 === 0) return false;

  const threshold = Math.sqrt(num);
  for (let i = 3; i <= threshold; i += 2) {
    if (num % i === 0) return false;
  }

  return true;
}

Let’s go over the code line by line.

First, we check if the number entered is a whole number using the isInteger() method available on the Number object. It returns a Boolean and if the number we enter is not an integer, we will return false as it cannot be a prime. (Note that we can return a custom message as well, like “Please enter an integer” but I wanted to keep it simple.)

The next if conditional returns false if the number entered is 1 or less. They cannot be primes.

The smallest prime number is 2, so we return true here. Why is it a good idea to filter for 2 and make it a standalone statement?

Two reasons. First, even numbers except 2 cannot be primes as they will all be divisible by not only 1 and itself but with 2. This means that even numbers greater than 2 will have at least three factors and primes have exactly two. As a result we can safely exclude all even numbers and this is done when the num % 2 === 0 check is present in the code. We will return false when such an even number is entered.

Secondly, we will have a for loop in the code which performs the actual search. By excluding the even numbers, we can increase i by 2 each time and since we start from 3, we will only consider odd numbers. This way we don’t have to check every single number and we can improve performance as well.

The block statement inside the for loop checks if the current number in the iteration (i.e. i) is a factor of num (the number we want to check for). If so, we will return false as it cannot be a prime number because we have found a factor other than 1 and num itself.

But we have a threshold or upper limit for the counter variable (i). Why would that be the square root of num?

One might think that we should go up to num or one less with the counter. But we don’t need to iterate that far. We are looking for factors (divisors) here. If we check for 12, 11 won’t ever be a factor. If we check for 3723, then 3722 won’t be a factor. I think you get the idea.

So how about iterating up to num / 3? The third of the number in question seems to be a reasonable choice, as we excluded all even numbers. For example, if we check for 33, the greatest factor (other than 33, of course) will be 33 / 3 = 11, so it might be enough to increase i up to 11.

But we can do even better. We only need to iterate over the numbers up to the square root. Why? It’s for the same reason as described in the last paragraph. Going back to our last example, 3 is a factor of 33, so 33 / 3 = 11 will be a factor, too.

isPrime only checks for a number being a prime. We are not concerned about the factors of the number. We are only interested in the number having a factor other than 1 or the number itself.

For every factor found that is less than the square root, we will find another factor which is greater than the square root of the number. The square root of 33 is approximately 5.74. 3 is less than the square root of 33 and 11 is greater. Every factor will have a “factor pair”.

As a result, if we can’t find any factors up to the square root of num, there won’t be any factors above too.

Finally, if any of the conditions are not met, we can return true because we have found a prime number.

Let’s check isPrime with the number mentioned above and with another one:

isPrime(3723) // false
isPrime(3719) // true

Finding the n-th prime

An interesting follow up on this problem is to find the n-th prime number. Project Euler lists this question as problem 7 on their website:

What is the 10001st prime number?

Understanding the problem

Let’s simplify the problem first and concentrate on finding the 10th prime number, which is 29. So when we call our function with 10 (getNthPrime(10)), we should get 29 as a result.

The easiest way to solve this problem is to start iterating over the positive whole numbers and if we find a prime using isPrime from the last section, we can increment the value of a counter. When the value of the counter reaches 10, we will simply return that prime number.

We might need to apply another iteration to cover this behaviour. If the counter variable is less than 10, we keep incrementing and checking the numbers if they are primes.

Code

The getNthPrime function can look like this:

function getNthPrime(n) {
  if (n === 1) return 2;

  let counter = 1;
  let j = 3;

  while (counter < n) {
    if (isPrime(j)) counter++;

    if (counter === n) return j;

    j += 2;
  }
}

The function accepts one argument, n, which is the number referring to the position of the relevant prime in the line. n should be a positive integer, otherwise the whole question just doesn’t make sense. In our case, n will be 10, because we are interested in finding the 10th prime number (which is still 29). getNthPrime works as follows.

If n is 1, we are interested in the first prime number, which is 2, so we will return 2. We can state this immediately to avoid iterating over the even numbers as they cannot be primes anyway.

We then set up our counter starting at 1 (because 2 is a prime and we need to include it) and j, which is the iterator variable. js initial value is 3 and we will increase its value by 2 each time to check for primes only among the odd numbers.

The while loop will work as long as counter is less than n. In these cases isPrime will check if the given j is a prime. If so, the value of counter is increased by 1.

Once counter becomes equal to 10, we simply return the current value of j, which will be the 10th prime.

Let’s see the function in action:

getNthPrime(10) // 29
getNthPrime(3) // 5
getNthPrime(20) // 71
getNthPrime(100) // 541
getNthPrime(1000) // 7919
getNthPrime(10001) // 104743

So the answer to the original question is 104743.

Largest prime factor

The Fundamental Theorem of Arithmetic declares that every integer greater than or equal to one can be written as a product of primes in exactly one way (aside from rearrangement). In practice, it means that an integer is either a prime or can be written as product of primes. For example, 10 = 2 * 5 or 36 = 2 * 2 * 3 * 3. We can change the order of the primes but it won’t change the result of the product.

Our job is to find the largest of such prime factors given a number.

Understanding the problem

We are not required to list all prime products of the given number although this might be the first idea. It’s enough if we start looking for the factors of the number and check if that factor is a prime.

We need the greatest of such numbers, so whenever we find a factor, we can use the abovementioned method of finding its “factor pair”. As a reminder, we first found the square root of the number and said if there was a factor, which is less than the square root, and then there must be another factor that is greater than the square root.

If we find a factor that is greater than the square root of the number, it will be a good candidate for the greatest prime factor (given it’s a prime). So we will check if such factor pairs exist and if so, we will check if they are primes.

We will also need a variable where we will store the current value of the greatest prime factor.

Let’s see how it works in the code.

Code

As with the example above, we will use the isPrime function.

function getLargestPrime(num) {
  if (!Number.isInteger(num) || num < 1) return 'Please enter a positive integer.';

  const limit = Math.sqrt(num);

  let largestPrime = 2;
  for (let i = 1; i <= limit; i++) {
    if (num % i === 0) {
      const largerFactor = num / i;

      if (isPrime(largerFactor)) {
        largestPrime = largerFactor;
        return largestPrime;
      }
      if (isPrime(i) && i > largestPrime) largestPrime = i;
    }
  }

  return largestPrime
}

We call the number we check the factors up to limit and the value of largestPrime is initially 2 as it’s the smallest prime. We will continually update its value as we go along.

No surprise inside the for statement. If we find a factor of num, we divide num by i to get its greater factor pair and store this value in largerFactor. If largerFactor is a prime, it becomes the greatest prime factor as well and we can return it. The reason for this is that we find the factors of num from smallest to greatest inside the for statement, therefore we will get the largest factor first upon dividing num with the current factor i.

If num is a prime number, we will return it since we start iterating at 1 and num / 1 equals num.

If largerFactor is not a prime number, we check if i, the smaller factor is a prime, and if so, we update the value of largestPrime with it.

We return largestPrime in the end.

Let’s have look at some examples:

getLargestPrime(16) // 2
getLargestPrime(29) // 29, it's a prime
getLargestPrime(258) // 43
getLargestPrime(600851475143) // 6857 Project Euler Problem 3

Conclusion

We have seen three little code snippets that are related to prime numbers. If you are not interested in mathematics, they are still good exercises to think about. And who knows, you might start being interested in them. :)

See you next time.