Условие задачи | | Прогресс |
Темы:
Простые числа и разложение на множители
Проверьте, является ли число простым.
Входные данные
Вводится одно натуральное число n не превышающее 2000000000 и не равное 1.
Выходные данные
Необходимо вывести строку prime , если число простое, или composite , если число составное.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
5 |
prime |
| |
|
Темы:
Простые числа и разложение на множители
Требуется разложить целое число N на простые множители, представив его в виде произведения простых множителей и вывести результат в порядке возрастания.
Входные данные
На вход падается число N (\(2 <= N <= 10^9\)).
Выходные данные
Выведите список простых множителей числа N в порядке неубывания, разделенных знаком «* ».
Примеры
№ |
Входные данные |
Выходные данные |
1 |
5 |
5 |
2 |
30 |
2*3*5 |
| |
|
Темы:
Простые числа и разложение на множители
Требуется разложить целое число N на простые множители, представив его в виде произведения степеней простых множителей и вывести результат в порядке возрастания.
Входные данные
На входе дано число N (\(2 <= N <= 10^9\)).
Выходные данные
Вывести разложение N на простые множители.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
2 |
2 |
2 |
1008 |
2^4*3^2*7 |
| |
|
Темы:
Простые числа и разложение на множители
Постулат Бертрана (теорема Бертрана-Чебышева, теорема Чебышева) гласит, что для любого \(n > 1\) найдется простое число p в интервале \(n < p < 2n\). Такая гипотеза была выдвинута в 1845 году французским математиком Джозефем Бертраном (проверившим ее до \(n=3000000\)) и доказана в 1850 году Пафнутием Чебышевым. Раманужан в 1920 году нашел более простое доказательство, а Эрдеш в 1932 – еще более простое.
Ваша задача состоит в том, чтобы решить несколько более общую задачу – а именно по числу n найти количество простых чисел p из интервала \(n < p < 2n\).
Напомним, что число называется простым, если оно делится только само на себя и на единицу
Входные данные
Целое число n (\(2 <= n <= 50000\)).
Выходные данные
Выведите одно число – ответ на задачу.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
3000 |
353 |
| |
|
Темы:
Простые числа и разложение на множители
Найти количество всех четырехзначных простых чисел, оканчивающиеся на цифру k .
Входные данные
Число k.
Выходные данные
Вывести число - количество простых чисел, удовлетворяющих условию задачи. Если таких чисел нет то вывести слово Absent .
Примеры
№ |
Входные данные |
Выходные данные |
1 |
1 |
266 |
2 |
0 |
Absent |
| |
|
Темы:
Простые числа и разложение на множители
Гипотеза Гольдбаха (не доказанная до сих пор) утверждает, что любое четное число (кроме 2) можно представить в виде суммы двух простых чисел.
Входные данные
Программа получает на вход одно натуральное четное число n (\(3<n<2 \cdot 10^5\)).
Выходные данные
Программа должна вывести два числа, разделенные пробелом. Числа должны быть простыми и давать в сумме n .
Примеры
№ |
Входные данные |
Выходные данные |
1 |
4 |
2 2 |
2 |
6 |
3 3 |
| |
|
Темы:
Простые числа и разложение на множители
Напишите программу, находящую количество троек целых чисел a , c , p таких, что p — простое число, числа удовлетворяют равенству: $$ \sqrt{a} - \sqrt{c} = \sqrt{p}. $$ Каждое из чисел a , c и p лежит в промежутке от N до M (то есть \(N<=a<= M,\ N<=c<= M,\ N<=p<= M\)).
Входные данные
Вводятся два целых числа N и M (\(0<=N<=M<=100000\)).
Выходные данные
Выведите искомое количество троек чисел a , c , p .
Примеры
№ |
Входные данные |
Выходные данные |
1 |
1 8 |
1 |
2 |
5 20 |
1 |
3 |
1 7 |
0 |
| |
|
Темы:
Простые числа и разложение на множители
Для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N , умноженное на себя N раз) делится на A .
Входные данные
На вход подается единственное число A (\(1 <= A <= 10^9\)).
Выходные данные
Необходимо вывести единственное число N .
Примеры
№ |
Входные данные |
Выходные данные |
1 |
8 |
4 |
2 |
13 |
13 |
| |
|
Темы:
Простые числа и разложение на множители
Из заданного набора чисел выберите одно, имеющее максимальное количество простых делителей. Например, 30 имеет три простых делителя (2, 3 и 5), а 40 – только два (2 и 5).
Входные данные
Первая строка содержит число N – количество чисел в наборе. Во второй строке теста содержится N чисел, разделенных пробелом. Все числа во входных данных целые, принимающие значения от 2 до 1024.
Выходные данные
В ответе выведите число с максимальным количеством простых делителей. Если таких чисел несколько, выведите наименьшее из них.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
10
3 5 7 9 11 13 15 17 19 21
|
15 |
2 |
11
2 4 6 8 10 13 39 105 200 201 143
|
105 |
| |
|
ID 38238.
2011
Темы:
Целые числа
Простые числа и разложение на множители
Представьте число 2011 в виду суммы K последовательных простых чисел (то есть простых чисел, между которыми нет других простых чисел). Например, число 31 можно представить в виде суммы трех посдедовательных простых чисел следующим образом: 7 + 11 + 13 = 31.
Входные данные
Вводится одно натуральное число K (от 1 до 2011).
Выходные данные
Выведите слагаемые в порядке возрастания, разделяя их пробелом.
Если разложить в сумму K слагаемых невозможно, выведите NO SOLUTION (заглавными буквами).
Примеры
№ |
Входные данные |
Выходные данные |
1 |
3 |
661 673 677 |
2 |
2 |
NO SOLUTION |
| |
|
Темы:
Простые числа и разложение на множители
У калькулятора есть две ячейки памяти: содержимое первой из них всегда отображается на табло, вторая является буфером. В начальный момент времени на табло калькулятора отображается целое число X, а в буфере записано число 0. У калькулятора работают только две клавиши: «+» и «=». При нажатии на «+» число, которое в данный момент отображено на табло, копируется в буфер. При нажатии на «=» число из буфера прибавляется к числу, отображенному на табло и результат отображается на табло, число в буфере при этом не меняется.
Требуется за наименьшее число нажатий клавиш на калькуляторе добиться того, чтобы на табло было отображено число Y.
Входные данные
Входной файл содержит два целых числа X и Y. Каждое из этих чисел по модулю не превышает 109.
Выходные данные
В первую строку выходного файла выведите одно число — количество нажатий клавиш, которое потребуется для получения числа Y. Если из числа X получить число Y с помощью указанных операций невозможно, в выходной файл выведите одно число –1.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
-1 -8 |
6 |
2 |
2 16 |
6 |
3 |
0 0 |
0 |
| |
|
Темы:
Простые числа и разложение на множители
Для того чтобы проверить, как ее ученики умеют считать, Мария Ивановна каждый год задает им на дом одну и ту же задачу — для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N, умноженное на себя N раз) делится на A. От года к году и от ученика к ученику меняется только число A.
Вы решили помочь будущим поколениям. Для этого вам необходимо написать программу, решающую эту задачу.
Формат входных данных
Во входном файле содержится единственное число A (1 ≤ A ≤ 1000000000 — на всякий случай; вдруг Мария Ивановна задаст большое число, чтобы кого-нибудь “завалить”).
Формат выходных данных
В выходной файл выведите единственное число N.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
8 |
4 |
2 |
13 |
13 |
| |
|
Темы:
Простые числа и разложение на множители
Пусть a1 = 2, a2 = 3, an = a1·a2·...·an-1 – 1 при n ≥ 3. Назовем числа ai псевдопростыми. Для заданного натурального числа X нужно ответить на вопрос: можно ли X однозначно представить в виде произведения псевдопростых чисел (представления, отличающиеся только порядком множителей, считаются одинаковыми), и, если можно — выдать разложение.<
Входные данные
Вводится одно натуральное число X, 1 < X ≤ 109.
Выходные данные
Выведите псевдопростые числа, произведение которых равно X, в произвольном порядке. Если разложения не существует или оно не единственно, выдать 0.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
6 |
2 3 |
2 |
5 |
5 |
3 |
7 |
0 |
| |
|
Темы:
Простые числа и разложение на множители
Цикл while
Найдите самый маленький натуральный делитель числа x, отличный от 1 (2 <= x <= 30000).
Входные данные
Вводится натуральное число x.
Выходные данные
Выведите наименьший делитель числа x, отличный от 1.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
6 |
2 |
| |
|
Темы:
Цикл for
Простые числа и разложение на множители
Условный оператор
Выведите все натуральные делители числа x в порядке возрастания (включая 1 и само число).
Входные данные
Вводится натуральное число x
Выходные данные
Выведите все делители числа x
Примеры
№ |
Входные данные |
Выходные данные |
1 |
32 |
1 2 4 8 16 32 |
| |
|
Темы:
Простые числа и разложение на множители
Цикл for
Подсчитайте количество натуральных делителей числа x (включая 1 и само число; x2109).
Входные данные
Вводится натуральное число x.
Выходные данные
Выведите единственное число - количество делителей числа x.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
32 |
6 |
| |
|