Простые числа и разложение на множители

Целое число \(x\) называется свободным от квадратов, если нет такого целого числа \(y > 1\), что \(x\) делится на \(y^2\), то есть \(x = y^2z\) для некоторого целого \(z\).

Даны числа \(l\) и \(r\). Требуется найти число пар целых чисел \((a, b)\), таких что \(l \le a < b \le r\), и числа \(a\), \(b\), а также их произведение \(ab\) свободны от квадратов.

Формат входных данных
На вход подается две строки, первая содержит целое число \(l\), а вторая "— целое число \(r\) (\(1 \le l < r \le 10^9\), \(r - l \le 1000\)).

Формат выходных данных
Выведите одно целое число — искомое число пар.

Примечание
В примере подходят пары \(a = 3, b = 5\), \(a = 5, b = 6\). Число \(4\) не может входить в пару, так как \(4 = 2^2\cdot 1\), а пара \(a = 3, b = 6\) не подходит, так как \(ab = 3\cdot 6 = 18 = 3^2\cdot 2\).

Будем называть два натуральных числа \(x\) и \(y\) непохожими, если они различны и нет двух различных отличных от \(1\) чисел \(a\) и \(b\), таких, что и \(x\) и \(y\) делятся как на \(a\), так и на \(b\). Например, 6 и 9 непохожи, так как единственное число, отличное от 1, на которое делятся оба числа "— 3. А вот числа 12 и 18 не являются непохожими, так как оба делятся на 2, 3 и 6.

Задано натуральное число \(x\), а также натуральные числа \(l\) и \(r\). Требуется найти все числа \(y\), такие что \(l \le y \le r\), и числа \(x\) и \(y\) непохожи.

Формат входных данных
На первой строке ввода задано число \(x\) (\(1 \le x \le 10^9\)).

На второй строке ввода задано число \(l\), на третьей строке ввода задано число \(r\) (\(1 \le l \le r \le 10^9\); \(r - l \le 1000\)).

Формат выходных данных
На первой строке выведите число \(k\) "— количество непохожих на \(x\) чисел на отрезке от \(l\) до \(r\), включительно.

На второй строке выведите все эти числа в возрастающем порядке.

У Деда Мороза есть N мешков с подарками. Каждый мешок имеет вес a1, a2, ..., aN. Для равномерной нагрузки на сани Деду Морозу необходимо, чтобы вес всех мешков был одинаковым. Чтобы этого добиться, Дед Мороз своим волшебным посохом может выполнить одну из следующих операций любое количество раз, возможно ноль раз.

• Дед Мороз может выбрать любой мешок и если его вес кратен двум, то уменьшить вес в два раза.
• Дед Мороз может выбрать любой мешок и если его кратен трем, то уменьшить вес в три раза.

На каждую операцию у Деда Мороза уходит 1 секунда.

Найдите минимальное общее количество секунд, которое необходимо Деду Морозу, для достижения одинакового веса всех мешков с подарками. Если нет способа достичь цели, выведите вместо этого значение -1.

Входные данные
Программа получает на вход в первой строке целое число N (2 <= N <= 1000). Во второй строке записаны N чисел ai - вес i-го мешка с подарками (1 <= ai <= 10⁹).


Выходные данные
Выведите ответ на задачу.
 
 

Примеры

№	Входные данные	Выходные данные
1	3 1 4 3	3
2	3 2 7 6	-1
3	6 1 1 1 1 1 1	0

Подсчитайте количество натуральных делителей числа x (включая 1 и само число x).

Входные данные
Вводится натуральное число x (x < 30000).

Выходные данные
Выведите единственное число - количество делителей числа x.
 

Примеры

№	Входные данные	Выходные данные
1	32	6

Выведите все натуральные делители числа x в порядке возрастания (включая 1 и само число).

Входные данные
Вводится натуральное число x

Выходные данные
Выведите все делители числа x

 

Примеры

№	Входные данные	Выходные данные
1	32	1 2 4 8 16 32

Найдите самый маленький натуральный делитель числа x, отличный от 1 (2 <= x <= 30000).

Входные данные
Вводится натуральное число x.

Выходные данные
Выведите наименьший делитель числа x, отличный от 1.

Примеры

№	Входные данные	Выходные данные
1	6	2

Пусть a₁ = 2, a₂ = 3, a_n = a_1·a₂·...·a_n-1 – 1 при n ≥ 3. Назовем числа ai псевдопростыми. Для заданного натурального числа X нужно ответить на вопрос: можно ли X однозначно представить в виде произведения псевдопростых чисел (представления, отличающиеся только порядком множителей, считаются одинаковыми), и, если можно — выдать разложение.<

Входные данные
Вводится одно натуральное число X, 1 < X ≤ 10⁹.

Выходные данные
Выведите псевдопростые числа, произведение которых равно X, в произвольном порядке. Если разложения не существует или оно не единственно, выдать 0.
 

Примеры

№	Входные данные	Выходные данные
1	6	2 3
2	5	5
3	7	0

Для того чтобы проверить, как ее ученики умеют считать, Мария Ивановна каждый год задает им на дом одну и ту же задачу — для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N, умноженное на себя N раз) делится на A. От года к году и от ученика к ученику меняется только число A.
Вы решили помочь будущим поколениям. Для этого вам необходимо написать программу, решающую эту задачу.
Формат входных данных
Во входном файле содержится единственное число A (1 ≤ A ≤ 1000000000 — на всякий случай; вдруг Мария Ивановна задаст большое число, чтобы кого-нибудь “завалить”).
Формат выходных данных
В выходной файл выведите единственное число N.
 

Примеры

№	Входные данные	Выходные данные
1	8	4
2	13	13

У калькулятора есть две ячейки памяти: содержимое первой из них всегда отображается на табло, вторая является буфером. В начальный момент времени на табло калькулятора отображается целое число X, а в буфере записано число 0. У калькулятора работают только две клавиши: «+» и «=». При нажатии на «+» число, которое в данный момент отображено на табло, копируется в буфер. При нажатии на «=» число из буфера прибавляется к числу, отображенному на табло и результат отображается на табло, число в буфере при этом не меняется.

Требуется за наименьшее число нажатий клавиш на калькуляторе добиться того, чтобы на табло было отображено число Y.

Входные данные
Входной файл содержит два целых числа X и Y. Каждое из этих чисел по модулю не превышает 10⁹.

Выходные данные
В первую строку выходного файла выведите одно число — количество нажатий клавиш, которое потребуется для получения числа Y. Если из числа X получить число Y с помощью указанных операций невозможно, в выходной файл выведите одно число –1.

Примеры

№	Входные данные	Выходные данные
1	-1 -8	6
2	2 16	6
3	0 0	0

Представьте число 2011 в виду суммы K последовательных простых чисел (то есть простых чисел, между которыми нет других простых чисел). Например, число 31 можно представить в виде суммы трех посдедовательных простых чисел следующим образом: 7 + 11 + 13 = 31.

Входные данные
Вводится одно натуральное число K (от 1 до 2011).

Выходные данные
Выведите слагаемые в порядке возрастания, разделяя их пробелом.

Если разложить в сумму K слагаемых невозможно, выведите NO SOLUTION (заглавными буквами).

Примеры

№	Входные данные	Выходные данные
1	3	661 673 677
2	2	NO SOLUTION

Для натурального числа N (1<=N<=10⁵) выведите на экран все его делители, включая 1 и само число N, в последней строке выведите количество этих делителей, включая 1 и само число N.

Входные данные
На вход подается натуральное число N (1<=N<=10⁵).

Выходные данные
В первой строке выведите все делители числа N, в порядке возрастания, разделяя их одним пробелом. Во второй строке выведите одно число - количество делителей исходного числа.
 

Примеры

№	Входные данные	Выходные данные
1	4	1 2 4 3

Дан массив чисел. Необходимо записать в другой массив все простые числа исходного массива. Если в исходном массиве нет простых чисел, программа должна вывести число 0.

Входные данные
Первая строка содержит размер массива N. Во второй строке через пробел задаются N натуральных чисел – элементы массива (все числа не превышают 1000). Гарантируется, что 0 < N ≤ 10000.

Выходные данные
Программа должна вывести в одну строчку все элементы нового массива, разделяя их пробелами. Если ни одного подходящего элемента в массиве не было, программа должна вывести число 0.
 

Примеры

№	Входные данные	Выходные данные
1	6 1 2 3 4 5 6	2 3 5

Гипотеза Гольдбаха (не доказанная до сих пор) утверждает, что любое четное число (кроме 2) можно представить в виде суммы двух простых чисел.

Входные данные 
Программа получает на вход одно натуральное четное число n (\(3<n<2 \cdot 10^5\)).

Выходные данные 
Программа должна вывести два числа, разделенные пробелом. Числа должны быть простыми и давать в сумме n.
 

Примеры

№	Входные данные	Выходные данные
1	4	2 2
2	6	3 3

Проверьте, является ли число простым.

Входные данные 
Вводится одно натуральное число n не превышающее 2000000000 и не равное 1.

Выходные данные 
Необходимо вывести  строку prime, если число простое, или composite, если число составное.
 

Примеры

№	Входные данные	Выходные данные
1	5	prime

Напишите программу, находящую количество троек целых чисел a, c, p таких, что p — простое число, числа удовлетворяют равенству: $$ \sqrt{a} - \sqrt{c} = \sqrt{p}. $$ Каждое из чисел a, c и p лежит в промежутке от N до M (то есть \(N<=a<= M,\ N<=c<= M,\ N<=p<= M\)).  

Примеры

№	Входные данные	Выходные данные
1	1 8	1
2	5 20	1
3	1 7	0

 

Примеры

№	Входные данные	Выходные данные
1	5	5
2	30	2*3*5

–Т—Л–≤–µ–і–Є—В–µ –і–≤–∞–і—Ж–∞—В—М –њ–µ—А–≤—Л—Е –њ—А–Њ—Б—В—Л—Е —З–Є—Б–µ–ї