| | | |
|
Постулат Бертрана
Простые числа и разложение на множители
Постулат Бертрана (теорема Бертрана-Чебышева, теорема Чебышева) гласит, что для любого 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 | |
![]()
|
|
Гипотеза Гольдбаха
Простые числа и разложение на множители
Гипотеза Гольдбаха (не доказанная до сих пор) утверждает, что любое четное число (кроме 2) можно представить в виде суммы двух простых чисел.
Входные данные
Программа получает на вход одно натуральное четное число n (3<n<2*105).
Выходные данные
Программа должна вывести два числа, разделенные пробелом. Числа должны быть простыми и давать в сумме n.
| |
![]()
|
|
Тройки чисел
Простые числа и разложение на множители
Напишите программу, находящую количество троек целых чисел a, c, p таких, что p — простое число, числа удовлетворяют равенству: $$ \sqrt{a} - \sqrt{c} = \sqrt{p} .$$
и каждое из чисел a, b и p лежит в промежутке от N до M (то есть N≤a≤ M, N≤b≤ M, N≤p≤ M)
Входные данные
Вводятся два целых числа N и M (0≤N≤M≤100000)
Выходные данные
Выведите искомое количество троек чисел a, c, p.
|
Ввод |
Вывод |
|
1 8 |
1 |
|
5 20 |
1 |
|
1 7 |
0 |
| |
![]()
|
|
Проверка на простоту
Простые числа и разложение на множители
Проверьте, является ли число простым.
Входные данные
Вводится одно натуральное число n не превышающее 2000000000 и не равное 1.
Выходные данные
Необходимо вывести строку prime, если число простое, или composite, если число составное.
| |
![]()
|
|
Степень числа
Простые числа и разложение на множители
Для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N, умноженное на себя N раз) делится на A. От года к году меняется только число A.
Вы решили помочь будущим поколениям. Для этого вам необходимо написать программу, решающую эту задачу.
Входные данные
Во входном файле содержится единственное число A (1 ≤ A ≤ 109 )
Выходные данные
В выходной файл необходимо вывести единственное число N.
| |
![]()
|
|
Разложение на простые
Простые числа и разложение на множители
Требуется разложить целое число N на простые множители, представив его в виде произведения простых множителей и вывести результат в порядке возрастания.
Входные данные
Программе дано число N (2 ≤ N ≤ 109).
Выходные данные
В выводе выведите список простых множителей числа N в порядке неубывания, разделенных знаком «*».
| |
![]()
|