## 1. Overview

Prime numbers exhibit interesting mathematical properties and find relevance in mathematical fields such as cryptography, financial algorithms, etc.

In this tutorial, we’ll learn how to check whether a number can be expressed as the sum of two prime numbers in Kotlin.

## 2. Understanding the Scenario

Let’s start by looking at a few numbers that are sum of two primes:

``val sumOfTwoPrimes = arrayOf(10, 13, 25, 28)``

In the sumOfTwoPrimes array, numbers 10, 13, 25, and 28 can be expressed as 3 + 7, 2 + 11, 2 + 23, and 11 + 17 respectively. Each is a sum of two prime numbers.

Now, let’s also look at the notSumOfTwoPrimes array for which the numbers can’t be defined as the sum of two primes:

``val notSumOfTwoPrimes = arrayOf(11, 27, 51, 57)``

In the following section, we’ll use these two arrays to validate each solution.

## 3. Using the Brute Force Approach

In this section, we’ll learn the brute force approach to solve our use case.

### 3.1. Algorithm

Let’s start by writing the checkPrimeUsingBruteForce() function to evaluate if a given number is prime or not:

``````fun checkPrimeUsingBruteForce(number: Int): Boolean {
if (number <= 1) return false
for (i in 2 until number) {
if (number % i == 0) {
return false
}
}
return true
}``````

In this approach, we check if the number is divisible by any of the numbers in the range [2, number).

Now, let’s write the function that uses the brute force algorithm to check if a number (n) can be expressed as the sum of two primes:

``````fun canBeExpressedAsSumOfTwoPrimesUsingBruteForceApproach(n: Int): Boolean {
for (i in 2..n / 2) {
if (checkPrimeUsingBruteForce(i) && checkPrimeUsingBruteForce(n - i)) {
return true
}
}
return false
}``````

We express n as the sum, (i) + (n – i), where i is in the range [2, n/2]. If both i and n-i are prime, then we return true.

### 3.2. Validation

First, we can check all the positive cases from the sumOfTwoPrimes array:

``````for (n in sumOfTwoPrimes) {
val result = canBeExpressedAsSumOfTwoPrimesUsingBruteForceApproach(n)
assertTrue(result)
}``````

Great! It looks like we got this one right.

Next, we can check the negative scenarios from the notSumOfTwoPrimes array:

``````for (n in notSumOfTwoPrimes) {
val result = canBeExpressedAsSumOfTwoPrimesUsingBruteForceApproach(n)
assertFalse(result)
}``````

Our approach looks correct.

## 4. Using the Sieve of Eratosthenes

In this section, we’ll use the ancient algorithm, Sieve of Eratosthenes, to find the prime numbers up to a limit. Further, we’ll use it to check if a number is the sum of two primes.

### 4.1. Algorithm

Let’s start by writing the sieveOfEratosthenes() function that takes an integer, n, as input and returns a BooleanArray:

``````fun sieveOfEratosthenes(n: Int): BooleanArray {
val primes = BooleanArray(n + 1) { true }
primes[0] = false
primes[1] = false
for (p in 2..n) {
if (primes[p]) {
for (i in p * p..n step p) {
primes[i] = false
}
}
}
return primes
}``````

We use a BooleanArray, primes, to mark whether a number is prime. Further, within the for loop, we mark all multiples of a prime number, p, within the range [2,n] as non-prime. In the end, we return primes.

Now, let’s write the function that uses the sieveOfEratosthenes() function to check if we can express n as the sum of two primes:

``````fun canBeExpressedAsSumOfTwoPrimesUsingSieveOfEratosthenes(n: Int): Boolean {
if (n < 2) return false
val primes = sieveOfEratosthenes(n)
for (i in 2 until n) {
if (primes[i] && primes[n - i]) {
return true
}
}
return false
}``````

For n < 2, we return false immediately. For higher numbers, we precompute the prime numbers in the primes array. As a result, we can efficiently determine if primes[i] is true for any i in the range [2,n). When both i and n-i are prime numbers, we return true.

### 4.2. Validation

Let’s verify our solution for all the numbers defined in the sumOfTwoPrimes array:

``````for (n in sumOfTwoPrimes) {
val result = canBeExpressedAsSumOfTwoPrimesUsingSieveOfEratosthenes(n)
assertTrue(result)
}``````

Fantastic! It gives the correct results.

Now, let’s also check that it’s working correctly for all numbers defined in the notSumOfTwoPrimes array:

``````for (n in notSumOfTwoPrimes) {
val result = canBeExpressedAsSumOfTwoPrimesUsingSieveOfEratosthenes(n)
assertFalse(result)
}``````

Great! As expected, our function returns false for this scenario.

## 5. Conclusion

In this article, we explored multiple approaches to check if a number can be expressed as the sum of two prime numbers. Specifically, we learned the brute force approach and the sieve of Eratosthenes while solving the use case.