#1787

Число

Темы: [Простые числа и разложение на множители]

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2006, Задача H ]

По заданным числам \(a\), \(b\), \(c\) и \(d\), найдите наименьшее натуральное число \(n\), большее \(ac\), которое нельзя представить в виде произведения двух натуральных чисел \(u\) и \(v\), таких что \(a\) ≤ \(u\) ≤ \(b\) и \(c\) ≤ \(v\) ≤ \(d\).

Входные данные

Входной файл содержит одну строку, состоящую из натуральных чисел \(a\), \(b\), \(c\), \(d\) (1 ≤ \(a\) ≤ \(b\) ≤ \(10^6\), 1 ≤ \(c\) ≤ \(d\) ≤ \(10^6\)).

Выходные данные

Выведите в выходной файл искомое число \(n\).

Примеры

Входные данные

1 2 1 2

Выходные данные

Входные данные

1 2 3 5

Выходные данные

#1834

Парные числа

Темы: [Простые числа и разложение на множители]

Назовём парой простого числа p такое простое число \(x\), что |\(p\) − \(x\)| = 2 . На отрезке [\(a\), \(b\)] найдите количество простых чисел, имеющих пару.

Входные данные

В единственной строке входного файла содержатся два натуральных числа \(a\) и \(b\) (2 \(\le\) \(a\) \(\le\) \(b\) \(\le\) 36 * \(10^6\)).

Выходные данные

Выведите единственное натуральное число — количество простых чисел, принадлежащих отрезку [\(a\), \(b\)], имеющих пару.

Примеры

Входные данные

2 10

Выходные данные

#1940

Последовательность-2

Темы: [Простые числа и разложение на множители]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2009-2010, Заочный этап, Тур 1, Задача H ]

Вася продолжает изобретать последовательности. Сегодня в школе его познакомили с операцией возведения в степень, и Вася придумал новую последовательность.

Сначала он пишет на доске натуральное число \(A\). Каждое следующее число, выписанное им на доске, будет равно степени с основанием \(A\) и показателем, равным предыдущему числу. Другими словами, последовательность будет выглядеть так:

\(x[1] = A\),

\(x[k + 1] = A^{x[k]}\), \(k\) > 0

После этого он решил узнать элемент этой последовательности с минимальным номером, который бы делился на данное число \(N\). Поскольку числа на доске могут быть довольно большими, без вашей помощи ему не обойтись.

Входные данные

Вводятся два натуральных числа \(A\), \(N\) (\(1\) ≤ \(A\) ≤ \(10^9\), \(1\) ≤ \(N\) ≤ \(10^9\)).

Выходные данные

Если ни один элемент последовательности не делится на \(N\), выведите 0. Иначе выведите минимальный номер элемента рассмотренной последовательности, делящегося на \(N\).

Примеры

Входные данные

2 2

Выходные данные

Входные данные

2 4

Выходные данные

#2873

Бактерии

Темы: [Простые числа и разложение на множители]

У юного биолога Антона в красивой стеклянной колбе живут n бактерий. Добавляя различные реактивы в колбу, Антон может контролировать число бактерий. Так, если p — некоторое простое число, то Антон умеет в домашних условиях получать вещество C_pH_2p+1OH, которое, будучи добавленным в колбу, уменьшает число бактерий ровно в p раз. Если же число бактерий не делилось на p, то результат действия вещества неопределен, и эксперимент теряет научную точность. Этого Антон допустить не желает, поэтому он применяет вещество C_pH_2p+1OH только когда число бактерий делится на p.

Кроме того, у Антона на кухне есть неограниченный запас диэтиламида лизергиновой кислоты (C₂0H₂₅N₃O). При добавлении в колбу с бактериями диэтиламида лизергиновой кислоты, число бактерий возводится в квадрат. Антон хочет, чтобы в колбе стало m бактерий. При этом он хочет добавлять какие-либо вещества в колбу наименьшее возможное число раз. Помогите ему сделать это.

Входные данные

Во входном файле содержатся два натуральных числа n и m (1 ≤ n, m ≤ 10⁹) — изначальное и желаемое число бактерий в колбе у Антона.

Выходные данные

Если получить ровно m бактерий невозможно, выведите в выходной файл слово «Impossible».

Если же искомый результат достижим, выведите кратчайшую последовательность добавлений веществ, которая позволяет его достичь, в следующем формате: добавление вещества C_pH_2p+1OH кодируется числом p, добавление вещества C₂0H₂₅N₃O — числом 0. Числа должны быть разделены пробелами и/или переводами строк.

Если существует несколько кратчайших последовательной добавлений веществ, оставляющих m бактерий, выведите любую из них.

Примеры

Входные данные

12 18

Выходные данные

2 0 2

Входные данные

56 6

Выходные данные

Impossible

#2903

Раскраска чисел

Темы: [Простые числа и разложение на множители]

Можно давать с гораздо меньшим TL

Профессор Васечкин хочет раскрасить целые числа от 1 до N таким образом, что если число A делится на число B, то числа A и B должны быть разного цвета. Помогите профессору найти такую раскраску, что число используемых цветов минимально.

Входные данные

Во входном файле записано число N (1 ≤ N ≤ 1000000).

Выходные данные

В первую строку выходного файла выведите M – число цветов в искомой раскраске. Во вторую строку выведите через пробел искомую раскраску чисел от 1 до N. Используемые числа должны быть обозначены числами от 1 до M.