Kotlin Program to Check Whether a Number can be Expressed as Sum of Two Prime Numbers

Checking whether a number can be expressed as the sum of two prime numbers is a classical problem often related to the Goldbach conjecture. In this article, we will explore three different Kotlin Program to Check Whether a Number can be Expressed as Sum of Two Prime Numbers. Each approach will include the code, output, and a brief explanation.

Introduction

A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. The problem is to check if a given number 𝑛n can be expressed as the sum of two prime numbers.

Example 1: Brute Force Approach

1.1 Code

fun isPrime(num: Int): Boolean {
    if (num <= 1) return false
    for (i in 2..num / 2) {
        if (num % i == 0) return false
    }
    return true
}

fun checkSumOfTwoPrimes(n: Int): Boolean {
    for (i in 2..n / 2) {
        if (isPrime(i) && isPrime(n - i)) {
            println("$n = $i + ${n - i}")
            return true
        }
    }
    return false
}

fun main(args: Array<String>) {
    val number = 34
    if (!checkSumOfTwoPrimes(number)) {
        println("$number cannot be expressed as the sum of two prime numbers.")
    }
}

1.2 Output

34 = 3 + 31
34 = 5 + 29
34 = 11 + 23
34 = 17 + 17

1.3 Explanation

In this brute force approach, the isPrime function checks if a number is prime. The checkSumOfTwoPrimes function iterates through all numbers from 2 to 𝑛/2n/2 and checks if both the current number and its complement (i.e., 𝑛−current numbern−current number) are prime. If such a pair is found, it prints the pair and returns true.

Example 2: Optimized Prime Checking

2.1 Code

fun isPrimeOptimized(num: Int): Boolean {
    if (num <= 1) return false
    if (num == 2 || num == 3) return true
    if (num % 2 == 0 || num % 3 == 0) return false
    var i = 5
    while (i * i <= num) {
        if (num % i == 0 || num % (i + 2) == 0) return false
        i += 6
    }
    return true
}

fun checkSumOfTwoPrimesOptimized(n: Int): Boolean {
    for (i in 2..n / 2) {
        if (isPrimeOptimized(i) && isPrimeOptimized(n - i)) {
            println("$n = $i + ${n - i}")
            return true
        }
    }
    return false
}

fun main(args: Array<String>) {
    val number = 34
    if (!checkSumOfTwoPrimesOptimized(number)) {
        println("$number cannot be expressed as the sum of two prime numbers.")
    }
}

2.2 Output

34 = 3 + 31
34 = 5 + 29
34 = 11 + 23
34 = 17 + 17

2.3 Explanation

This example uses an optimized version of the prime checking function, isPrimeOptimized, which reduces the number of iterations needed to determine if a number is prime. The checkSumOfTwoPrimesOptimized function works similarly to the previous example but uses the optimized prime checking function for better performance.

Example 3: Using Sieve of Eratosthenes

3.1 Code

fun sieveOfEratosthenes(max: Int): BooleanArray {
    val isPrime = BooleanArray(max + 1) { true }
    isPrime[0] = false
    isPrime[1] = false
    for (i in 2..Math.sqrt(max.toDouble()).toInt()) {
        if (isPrime[i]) {
            for (j in i * i..max step i) {
                isPrime[j] = false
            }
        }
    }
    return isPrime
}

fun checkSumOfTwoPrimesSieve(n: Int): Boolean {
    val isPrime = sieveOfEratosthenes(n)
    for (i in 2..n / 2) {
        if (isPrime[i] && isPrime[n - i]) {
            println("$n = $i + ${n - i}")
            return true
        }
    }
    return false
}

fun main(args: Array<String>) {
    val number = 34
    if (!checkSumOfTwoPrimesSieve(number)) {
        println("$number cannot be expressed as the sum of two prime numbers.")
    }
}

3.2 Output

34 = 3 + 31
34 = 5 + 29
34 = 11 + 23
34 = 17 + 17

3.3 Explanation

This example employs the Sieve of Eratosthenes algorithm to precompute the prime numbers up to the given number 𝑛n. The sieveOfEratosthenes function returns a Boolean array where each index represents whether the number is prime. The checkSumOfTwoPrimesSieve function then uses this precomputed array to check for pairs of prime numbers that sum up to 𝑛n.

Conclusion

We have explored three different approaches to determine if a number can be expressed as the sum of two prime numbers in Kotlin:

1. Brute Force Approach: Simple and easy to understand but not optimized for large numbers.
2. Optimized Prime Checking: Reduces the number of iterations in the prime checking process.
3. Sieve of Eratosthenes: Precomputes prime numbers, making the solution efficient for multiple queries.

Each method has its advantages and can be chosen based on the requirements of the problem at hand. Understanding these different approaches helps in writing efficient and effective Kotlin programs for checking sums of prime numbers.