Все задачи
Средне Решено: 0 Процент решений: 0%

Разложение Гольдбаха

Представьте чётное число в виде суммы двух простых так, чтобы первое простое было как можно меньше.

Чему вы научитесь

  • Писать проверку на простоту перебором делителей до √n
  • Перебирать кандидатов по возрастанию и останавливаться на первом подходящем
  • Возвращать пару в нужном порядке

Условие

Гипотеза Гольдбаха утверждает, что любое чётное число больше 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 чётное

Примеры

Пример 1
Ввод:
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].

Пример 2
Ввод:
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. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.