Гипотеза Гольдбаха утверждает, что любое чётное число больше 2 можно представить в виде суммы двух простых чисел. Она до сих пор не доказана, но проверена далеко за пределами чисел из этой задачи. Часто способов несколько: 28 = 5 + 23 = 11 + 17. Найдите тот, в котором меньшее простое слагаемое минимально.
Реализуйте goldbach_partition(n).
Перебор p = 2, 3, 5, ... с проверкой, простое ли n − p, быстро находит ответ, потому что маленькое p почти всегда подходит. Чтобы проверить на простоту число до 10^9 перебором делителей, достаточно делителей примерно до 31 623.
Входные данные
n: чётное число больше 2.
Выходные данные
Верните [p, q], где p и q простые, p + q = n, p ≤ q и p является наименьшим простым числом, для которого это возможно.
Ограничения
4 ≤ n ≤ 10^9, n чётное
Примеры
Ввод:
n = 28
Ожидаемый вывод:
expected = [5, 23]
Ввод:
long long n = 28;
Ожидаемый вывод:
std::vector<long long> expected = {5, 23};
Ввод:
long n = 28;
Ожидаемый вывод:
long[] expected = new long[] {5, 23};
Пояснение
28 − 2 = 26 и 28 − 3 = 25 не простые, а 28 − 5 = 23 простое, поэтому ответ [5, 23].
Ввод:
n = 4
Ожидаемый вывод:
expected = [2, 2]
Ввод:
long long n = 4;
Ожидаемый вывод:
std::vector<long long> expected = {2, 2};
Ввод:
long n = 4;
Ожидаемый вывод:
long[] expected = new long[] {2, 2};
Пояснение
Единственный вариант 2 + 2, поэтому ответ [2, 2].
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Перебирайте p = 2, 3, 4, ... и остановитесь на первом p, при котором и p, и n − p простые.
Подсказка 2
При проверке на простоту достаточно перебирать делители до квадратного корня.
Подсказка 3
Раз вы останавливаетесь на наименьшем p, условие p ≤ n − p выполняется само собой.
Ожидаемая сложность
время O(k √n), где k равно количеству проверенных кандидатов, доп. память O(1)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.