Помните двух программистов и их диалог про возраст сыновей? Они встретились снова! Вот их история.
Двоих программистов вывезли на кладбище бандиты из девяностых. Бандиты тайно выбрали 2 целых положительных числа, оба больше единицы, а их сумма меньше 100. Первому программисту бандит сказал произведение этих чисел, а второму — их сумму. После этого у программистов состоялся такой разговор.
Первый: Я понятия не имею, какая у тебя сумма.
Второй: Ха-ха, это для меня не новость! Я и так знал, что ты не знал этого.
Первый: Ага! Теперь я понял, чему равна твоя сумма!
Второй: Отлично — теперь и я тоже знаю твоё произведение!
Бандиты, конечно же, их отпустили. Потому что это загадка! А загадка в том, что это за числа и как программисты это выяснили.
В отличие от предыдущей задачи, здесь решение намного сложнее, потому что в голове нужно держать одновременно 2-3 условия, которыми надо проверять числа. Но мы справимся.
Для решения нам понадобится вспомнить, что такое простые числа и в чём их особенность. Простое число — то, которое может делиться нацело только на себя и на единицу. Например, число 5 — простое, потому что делится только на 5 и на 1. А число 6 — не простое, потому что кроме 6 и 1 оно ещё делится на 2 и 3 без остатка. Семь тоже будет простым числом, а восемь — нет, потому что кроме 8 и 1 оно делится также на 2 и 4.
Если перемножить два простых числа, то полученное произведение больше никак нельзя получить другим способом (кроме умножения этого же числа на единицу). Поясним на примере.
Возьмём два простых числа 5 и 7 и перемножим их — получится 35. Больше число 35 получить никак не получится, кроме как умножить 35 на 1. Это значит, что если произведение можно разложить на два простых множителя, то других вариантов разложения (кроме числа и единицы) у него не будет. Это нам пригодится при решении задач — и если число можно разложить на 2 простых, то и их сумму тоже легко сразу посчитать.
Ещё пример:
54 = 2 × 27
54 = 3 × 18
54 = 6 × 9, а это значит, что число 54 нельзя получить перемножением двух простых чисел и нельзя сразу сказать, чему однозначно равна сумма множителей.
И ещё:
21 = 3 × 7
Оба числа простые, поэтому произведение 21 можно получить только из них, а значит, легко посчитать сумму — она будет равна 3 + 7 = 10.
Теперь переведём их диалог на язык математики и логики и обозначим числа как n и m:
Первый: Я понял, что одно из чисел точно не простое, потому что иначе я сразу бы разложил число на произведение двух простых и легко получил сумму. А раз так, то это одно из чисел m или n можно получить перемножением двух других чисел. Поэтому общее произведение состоит не менее чем из трёх множителей, причём как минимум один из них отличается от остальных — поэтому получается несколько вариантов возможных сумм, и я не знаю, какая из них правильная (пометим это как Правило 1).
Второй: Сумму, которая у меня есть, нельзя получить из двух простых чисел, поэтому и твоё произведение тоже нельзя разложить на два простых множителя. Это значит, что у меня нечётная сумма, потому что, по гипотезе Гольдбаха, в нашем случае можно получить любое чётное число, сложив два простых. А раз это не два простых числа, значит, и сумма будет нечётная. А ещё эта сумма точно не равна сумме двух и простого числа, потому что два — тоже простое, ха! Поэтому есть несколько вариантов суммы m и n, которые подходят под твои условия, но я не могу пока определить, какие именно (пометим это как Правило 2).
Первый: Из всех множителей моего произведения я могу составить только один вариант пары, сумма которой подойдёт под твоё ограничение — не будет разбиваться на сумму двух простых или сумму чисел одного множителя (Правило 3).
Второй: Ах вот как! Из всех вариантов пар, на которые можно разбить сумму и подходящих под твои условия, есть только одна, которая позволила бы тебе определить это (Правило 4). Теперь и мне понятно, что это за числа!
Теперь подберём варианты суммы, которая была у второго. Ограничения такие:
- нечётная;
- не равна сумме двойки и простого числа.
1 — не подходит, потому что оба числа больше единицы.
2, 4, 6, 8… — нет, потому что чётные.
3 — нет, потому что это сумма двойки и простого числа.
5 — нет, по той же причине (2 + 3).
7 — тоже нет (2 + 5).
9 — тоже нет (2 + 7, а 7 — простое число).
11 — подходит.
13 — нет, потому что 13 = 2 + 11 (11 — простое число).
15 — нет, потому что 15 = 2 + 13 (13 — тоже простое число).
17 — подходит.
19 — нет, потому что 19 = 2 + 17 (17 — простое число).
…
Способ подбора суммы понятен, дальше можно продолжать по тому же алгоритму. Мы же выберем те, которые нам уже подошли, и на их примере покажем, что нужно делать дальше, чтобы получить правильный ответ. Наши числа, которые нам подходят уже сейчас: 11 и 17. Начнём с 11.
Сумма = 11.
Найдём все слагаемые, которые могут давать эту сумму:
2 + 9
3 + 8
4 + 7
5 + 6
Для каждого из них запишем произведение и проверим, выполняется ли Правило 3, которое сказал первый программист.
Смотрим на произведение 2 × 9 = 18 и как ещё его можно получить.
18 = 2 × 9 → Да (Правило 3 выполняется).
18 = 3 × 6 → Нет (Правило 3 не работает, потому что 3 + 6 = 9, а 9 можно получить из простых чисел 2 и 7).
Смотрим на произведение 3 × 8 = 24.
24 = 2 × 12 → Нет (чётная сумма, Правило 2 не работает).
24 = 3 × 8 → Да (выполняется Правило 3).
24 = 6 × 4 → Нет (чётная сумма).
Смотрим на произведение 4 × 7 = 28.
28 = 2 × 14 → Нет (чётная сумма).
28 = 4 × 7 → Да (выполняется Правило 3).
Смотрим на произведение 5 × 6 = 30.
30 = 2 × 15 → Да.
30 = 3 × 10 → Нет (Правило 3 не работает, потому что 3 + 10 = 13, а 13 можно получить суммой простых чисел 2 и 11).
30 = 5 × 6 → Да.
Тут мы вообще не можем выбрать одну пару, потому что Правило 3 выполняется 2 раза, а значит, этот вариант отбрасываем.
Получается, что для суммы 11 могут быть три варианта произведений, для которых выполняется Правило 3: 2 и 9, 3 и 8, 4 и 7. Но тогда Правило 4 не выполняется, потому что нужно, чтобы для одной суммы была только одна пара, которая подходит под правило 3. Продолжаем искать.
Сумма = 17.
Найдём все слагаемые, которые могут давать эту сумму:
2 + 15
3 + 14
4 + 13
5 + 12
6 + 11
7 + 10
8 + 9
Для каждого из них запишем произведение и проверим, выполняется ли Правило 3, которое сказал первый программист.
Смотрим на произведение 2 × 15 = 30 и как ещё его можно получить.
30 = 2 × 15 → Да.
30 = 3 × 10 → Нет (Правило 3 не работает, потому что 3 + 10 = 13, а 13 можно получить суммой простых чисел 2 и 11).
30 = 5 × 6 → Да.
Тут мы вообще не можем выбрать одну пару, потому что Правило 3 выполняется 2 раза, а значит, этот вариант отбрасываем.
Смотрим на произведение 3 × 14 = 42 и как ещё его можно получить:
42 = 2 × 21 → Да.
42 = 3 × 14 → Да.
42 = 6 × 7 → Нет.
Два раза выполняется Правило 3 — отбрасываем пару.
Смотрим на произведение 4 × 13 = 52 и как ещё его можно получить.
52 = 2 × 26 → Нет.
52 = 4 × 13 → Да.
Смотрим на произведение 5 × 12 = 60 и как ещё его можно получить.
60 = 2 × 30 → Нет.
60 = 3 × 20 → Да.
60 = 5 × 12 → Да.
60 = 6 × 10 → Нет.
Два раза выполняется Правило 3 — отбрасываем пару.
Смотрим на произведение 6 × 11 = 66 и как ещё его можно получить.
66 = 2 × 33 → Да.
66 = 3 × 22 → Нет.
66 = 6 × 11 → Да.
Два раза выполняется Правило 3 — отбрасываем пару.
Смотрим на произведение 7 × 10 = 70 и как ещё его можно получить.
70 = 2 × 35 → Да.
70 = 5 × 14 → Нет.
70 = 7 × 10 → Да.
Два раза выполняется Правило 3 — отбрасываем пару.
Смотрим на произведение 8 × 9 = 72 и как ещё его можно получить.
72 = 2 × 36 → Нет.
72 = 3 × 24 → Да.
72 = 4 × 18 → Нет.
72 = 6 × 12 → Нет.
72 = 8 × 9 → Да.
Два раза выполняется Правило 3 — отбрасываем пару.
Получается, что для суммы 17 может быть только один вариант произведения, для которого выполняется Правило 3: это 4 и 13. А значит, что Правило 4 тоже выполняется и мы нашли нужные числа!
Если вы дочитали досюда и всё поняли — снимаем шляпу. Вы не из тех, кого могут испугать вычисления и логический подход!
