在Kotlin中检查一个数是否可以表示为两个质数之和

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.

Persistence

REST

Security