GoldConjecture
SRM 130 · 2003-01-25 · by brett1479
SRM 130 · 2003-01-25 · by brett1479 · Simple Math
Problem Statement
Problem Statement
A famous mathematical conjecture states that all numbers greater than 5 can be expressed as the sum of 3 prime numbers. A number is prime if it is only evenly divisible by itself and 1. Furthermore, 2 is the lowest prime number. Given an integer k greater than 5, you will return the 3 prime numbers whose sum is k in increasing order. If there is more than one combination of three primes whose sum is k return the 3 primes with the highest product (i.e., the three primes multiplied together produces the highest value).
Constraints
- k will be between 6 and 2000 inclusive
- All given values of k will have solutions
Examples
0)
10
Returns: { 2, 3, 5 }
2,3,5 is the only solution that works.
1)
157
Returns: { 43, 53, 61 }
2)
12
Returns: { 2, 5, 5 }
2,3,7 and 2,5,5 both are primes that add up to 12 but: 2*3*7 = 42 2*5*5 = 50 So the solution is {2,5,5}
3)
2000
Returns: { 2, 977, 1021 }
4)
1997
Returns: { 659, 661, 677 }
Submissions are judged against all 36 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class GoldConjecture with a public method vector<int> numbers(int k) · 36 test cases · 2 s / 256 MB per case