# Three exercises with primes numbers

Although prime numbers can lead to extremely difficult mathematical proofs and formulas, their basic concept is simple enough to practice one's algorithmic skills. Three little prime-related exercises will follow below the fold.

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. `j`s 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.