Link to kata: link
Rank: 6 kyu
Kata author: @rsalgado
I have been recently learning Ruby-lang and have been attempting to solve the following kata from Codewars involving Goldbach's Conjecture:
Goldbach's Conjecture is amongst the oldest and [most] well-known unsolved mathematical problems out there. In correspondence with Leonhard Euler in 1742, German mathematician Christian Goldbach made a conjecture stating that:
"Every even integer greater than 2 can be written as the sum of two primes"
which is known today as the (strong) Goldbach conjecture.
...
Your task is to implement the function in the starter code, taking into account the following:
- If the argument isn't even [or isn't] greater than 2, return an empty array/tuple.
- For arguments even and greater than 2, return a two-element array/tuple with two prime numbers whose sum is the given input.
- The two prime numbers must be the farthest ones (the ones with the greatest difference).
- The first prime number must be the smallest one.
The following test cases are given in the description and in the example test cases:
check_goldbach(2) == []
check_goldbach(4) == [2, 2]
check_goldbach(5) == []
check_goldbach(6) == [3, 3]
check_goldbach(8) == [3, 5]
check_goldbach(10) == [3, 7]
check_goldbach(14) == [3, 11]
check_goldbach(15) == []
check_goldbach(24) == [5, 19]
From my testing, it seems that the random tests include numbers in the range$10ドル^5\le\text{input}\lt10^9$$although I'm not entirely sure.
Here is my current solution that gets Time Limit Exceeded:
def check_goldbach num
"""
The strong Goldbach's Conjecture is stated
as follows:
- Every even integer greater than 2 can
be written as the sum of two primes.
This was conjectured by German mathematician
Christian Goldbach in 1742 in correspondence
with Leonhard Euler.
==========================================
`check_goldbach` is a function that takes
in an integer `num` and returns either of
- An empty array, if `num` is odd, is less than
or equal to 2, or if the strong version of
Goldbach's Conjecture is False.
- An array of two integers [i, j], where `i` and `j`
are both prime, `i + j == num` and `i <= j`.
==========================================
We do this by first using a prime number sieve to
generate an array of prime numbers. Then, for each
prime number `i` in the range [2, sieve.length / 2],
we check if `num - i` is prime.
If it is, then we return `[i, num - i]`. However,
if Goldbach's conjecture is false (we have checked
all of the numbers in the list and `num - i` is never
prime), we finally return an empty array.
==========================================
Examples:
puts check_goldbach(2) # []
puts check_goldbach(4) # [2, 2]
puts check_goldbach(5) # []
puts check_goldbach(6) # [3, 3]
puts check_goldbach(8) # [3, 5]
puts check_goldbach(10) # [3, 7]
puts check_goldbach(14) # [3, 11]
puts check_goldbach(15) # []
puts check_goldbach(24) # [5, 19]
"""
# If the input is odd or not greater than 2.
if num % 2 == 1 or num < 3
return []
end
sieve = Array.new(num, true)
# By definition, 0 and 1 are not prime.
sieve[0] = sieve[1] = false
# If some `i` = `p*k` for prime `p` and
# `k > 1`, then `i` is not prime.
(4...num).step(2) {|i| sieve[i] = false}
(3...Math.sqrt(num).to_i).step(2) do |i|
if sieve[i]
(i*i...num).step(2*i) {|j| sieve[j] = false}
end
end
# For each prime `i` in the interval `[2, sieve.length / 2]`,
# we check if `num - i` is also prime.
# We select the primes from 2 up to including `sieve.length` / 2
# as then we don't have to take more prime numbers than we need,
# since we are not modifying the sieve itself.
primes = (2..sieve.length / 2).select {|i| sieve[i]}
primes.each do |i|
if sieve[num - i]
return [i, num - i]
end
end
# The conjecture is false, likely will never happen.
puts "The conjecture is false for input #{num}."
return []
end
My question is: How can I improve the execution speed of the function?
While I am currently passing all 8 static test-cases (that is, the smaller test-cases in the full test suite) in around 2-3.5 milliseconds, I still usually only pass 2 to 4 random test-cases in the other 11.996 to 11.998 seconds before timing out, depending on how large the random numbers are.
2 Answers 2
Using a prime sieve isn't always useful
It ends up taking a LOT of memory, and consequently a lot of time to generate large arrays and then iterate through them to create the sieves.
Instead I could have just written a simple prime checker like so:
def is_prime num
if num < 2
return false
end
if num == 2 or num == 3
return true
end
(2..Math.sqrt(num).to_i + 1).each do |i|
if n % i == 0
return false
end
end
return true
end
since I don't necessarily need to know what numbers in the range (0..n) are prime.
And then I could just check (if num != 2 and num % 2 == 0) for each possible_prime in the interval [2, num / 2] to check if both possible_prime and num - possible_prime are both prime numbers.
In total, making these changes causes the code to be successful on all tests in a total time of 56.3841 milliseconds (server side).
Final iteration of the code:
def is_prime num
if num < 2
return false
end
if num == 2 or num == 3
return true
end
(2..Math.sqrt(num).to_i + 1).each do |i|
if n % i == 0
return false
end
end
return true
end
def check_goldbach num
"""
The strong Goldbach's Conjecture is stated
as follows:
- Every even integer greater than 2 can
be written as the sum of two primes.
This was conjectured by German mathematician
Christian Goldbach in 1742 in correspondence
with Leonhard Euler.
==========================================
`check_goldbach` is a function that takes
in an integer `num` and returns either of
- An empty array, if `num` is odd, is less than
or equal to 2, or if the strong version of
Goldbach's Conjecture is False.
- An array of two integers [i, j], where `i` and `j`
are both prime, `i + j == num` and `i <= j`.
==========================================
We do this by first using a prime number sieve to
generate an array of prime numbers. Then, for each
prime number `i` in the range [2, sieve.length / 2],
we check if `num - i` is prime.
If it is, then we return `[i, num - i]`. However,
if Goldbach's conjecture is false (we have checked
all of the numbers in the list and `num - i` is never
prime), we finally return an empty array.
==========================================
Examples:
puts check_goldbach(2) # []
puts check_goldbach(4) # [2, 2]
puts check_goldbach(5) # []
puts check_goldbach(6) # [3, 3]
puts check_goldbach(8) # [3, 5]
puts check_goldbach(10) # [3, 7]
puts check_goldbach(14) # [3, 11]
puts check_goldbach(15) # []
puts check_goldbach(24) # [5, 19]
"""
# If the input is odd or not greater than 2.
if num % 2 == 1 or num < 3
return []
end
possible_prime = 2
while possible_prime <= num / 2
if is_prime(possible_prime)
if is_prime(num - possible_prime)
return [possible_prime, num - possible_prime]
end
end
possible_prime += 1
end
puts "The conjecture is false for input #{num}"
return []
end
N ≥ 6 would have to be the sum of two odd primes. An odd number x is prime with probability about 2/ln x. X and n - x are two primes with probability about 1 / ln2 n, so you need to examine about ln2 n pairs of numbers to find a pair of primes.
So that shows that creating a sieve of size n is very inefficient. It takes n steps when you usually need just ln2 n. So create one sieve for the numbers cxln2 n and one for the numbers n - cx ln2 n to n. Experiment to find a "c" that usually finds a solution, and if it doesn’t work then repeat with 2c instead of c.
Now if you wanted to check all even 6 ≤ N ≤ 109 then you would create one large sieve.
Explore related questions
See similar questions with these tags.
primemodule until I completed the kata and looked at other people's solutions. \$\endgroup\$