August 26, 2024
P40 - Goldbach's conjecture.
Goldbach's conjecture says that every positive even number greater than 2 is the sum of two prime numbers. E.g. 28 = 5 + 23. It is one of the most famous facts in number theory that has not been proved to be correct in the general case. It has been numerically confirmed up to very large numbers (much larger than Kotlin's Int can represent). Write a function to find the two prime numbers that sum up to a given even integer.
> 28.goldbach()
(5, 23)kotlin
package org.kotlin99.arithmetic
import com.natpryce.hamkrest.assertion.assertThat
import com.natpryce.hamkrest.equalTo
import org.junit.Test
fun Int.goldbach(): Pair<Int, Int> {
if (this == 2) return Pair(1, 1)
if (this == 3) return Pair(1, 2)
val prime = listPrimesInRange(2 until this).find { (this - it).isPrime() } ?: throw IllegalStateException()
return Pair(prime, this - prime)
}
class P40Test {
@Test fun `Goldbach's conjecture`() {
assertThat(4.goldbach(), equalTo(Pair(2, 2)))
assertThat(28.goldbach(), equalTo(Pair(5, 23)))
}
}
Be first to comment