Prime Number Check

Do you know what a prime number is ? Unless you work with cryptography algorithms or a similar field, chances are that you have not heard about prime number since the high school. A significant number of whiteboard coding questions rely on prime numbers, so this will be a good refresher. A prime number is a natural number that has no positive divisors other than 1 and itself.

• Number 7 is a prime number.
• Number 15 is not! It can be divided by 5 and 3.

The Prime Number Check

Write a method that checks if a number is a prime number.

We will test every natural number below the number we want to test. The number is prime id it can be divided by at least one of these natural numbers. Translating this into code:

public Boolean isPrime(Integer n) {
  boolean isPrime = true;
  for (int i = n - 1; i > 1; i--) {
    if (n % i == 0) {
      isPrime = false;
      break;
    }
  }
  return isPrime;
}

You may have noticed this implementation is extremely inefficient for large numbers. We will come back to this exercise at a later lecture to see what we can do about that.

You can find another exercise relying on prime numbers here.