Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

Постулат Бертрана

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

Постулат Бертрана (теорема Бертрана-Чебышева, теорема Чебышева) гласит, что для любого n > 1 найдется простое число p в интервале n < p < 2n. Такая гипотеза была выдвинута в 1845 году французским математиком Джозефем Бертраном (проверившим ее до n=3000000) и доказана в 1850 году Пафнутием Чебышевым. Раманужан в 1920 году нашел более простое доказательство, а Эрдеш в 1932 – еще более простое.

Ваша задача состоит в том, чтобы решить несколько более общую задачу – а именно по числу n найти количество простых чисел p из интервала n < p < 2n.

Напомним, что число называется простым, если оно делится только само на себя и на единицу

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

целое число n (2 ≤ n ≤ 50000).

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

выведите одно число – ответ на задачу.

Простые числа - 2

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

Знаете ли вы, что такое простое число? Простое число – это натуральное число, имеющее ровно два различных натуральных делителя: единицу и самого себя. Все остальные числа, кроме единицы, называются составными. Например, числа 2, 3, 5, 7, 11 являются простыми. А числа 4, 6, 10 – составными.
 
Требуется из заданного набора чисел выбрать одно, имеющее максимальное количество простых делителей. Например, 30 имеет три простых делителя (2, 3 и 5), а 40 – только два (2 и 5).
 
Входные данные
Первая строка  содержит число N – количество чисел в наборе. Во второй строке теста содержится N чисел, разделенных пробелом. Все числа во входных данных целые, принимающие значения от 2 до 1024.
 
Выходные данные
В ответе выведите число с максимальным количеством простых делителей. Если таких чисел несколько, выведите наименьшее из них.

Ввод Вывод
10
3 5 7 9 11 13 15 17 19 21
15
11
2 4 6 8 10 13 39 105 200 201 143
105

http://acmp.ru/index.asp?main=task&id_task=938

Тройки чисел

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

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

Входные данные
Вводятся два целых числа N и M (0≤N≤M≤100000)
 
Выходные данные
Выведите искомое количество троек чисел a, c, p.
 
Ввод Вывод
1 8 1
5 20  1
1 7 0