## 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.

As always, the code from this article is availableÂ over on GitHub.