На уроке информатики Фоме задали задачу о проверке гипотезы Гольдбаха.
Условие задачи выглядело так:
Гипотеза Гольдбаха (не доказанная до сих пор) утверждает, что любое четное число (кроме 2) можно представить в виде суммы двух простых чисел.
Фома легко решил данную задачу методом поиска "первого решения".
Дома, Фома заметил, что во время отладки, он получал решения, в которых одно из чисел было не очень большим.
Так, для числа 1000000, он получил разложение 1000000=17+999983. Фома решил проверить, в чем сложность гипотезы Гольдбаха.
Для этого Фома придумал задачу:
Определим функцию g(n) = количеству разложений числа n в сумму двух простых чисел. (разложения, отличающиеся порядком слагаемых, считаются одинаковыми).
На отрезке натуральных чисел от A до B найдите чётное число x такое, что: g(x) кратно 5 и имеет минимальное значение среди всех g(x) кратных 5 на этом отрезке.
Решите задачу Фомы.
Входные данные
Границы отрезка A, B (два натуральных числа 5≤ A<B≤106 )
Выходные данные
- "Impossible" если для всех чётных x из отрезка [A;B] значение g(x) не кратно 5.
- два числа - x, g( x ) ( g(x) кратно 5 и минимальное для A≤ x≤B). Если таких x несколько, то выведите минимальное значение x.
Примеры
| № |
Входные данные |
Выходные данные |
Примечание |
| 1 |
5 10 |
Impossible |
На отрезке всего три четных числа (6, 8, 10)
Число 8 =3+5 и других представлений нет (5+3 считается таким же как 3+5)
Для 10 есть два представления (3+7 и 5+5)
Таким образом значений x, при которых g(x) кратно 5 нет. |
| 2 |
20 60 |
48 5 |
g(x) может принимать значения меньшие 3 (g(20)=2)
g(x)=5 для x из множества {48, 54}. 48 -минимальное значение |
| 3 |
2000 2005 |
Impossible |
|