Дано натуральное число \(n>1\). Выведите его наименьший простой делитель.
Решение оформите в виде функции MinDivisor(n). Алгоритм должен иметь сложность \(O(\sqrt{n}) \).
Указание. Если у числа \(n\) нет делителя не превосходящего \(\sqrt{n}\), то число \(n\) — простое и ответом будет само число \(n\).
Вводится натуральное число.
Выведите ответ на задачу.
| Ввод | Вывод |
|---|---|
4 |
2 |
5 |
5 |
Выведите все натуральные делители числа x в порядке возрастания (включая 1 и само число).
Вводится натуральное число.
Выведите все делители числа x
| Ввод | Вывод |
|---|---|
32 |
1 2 4 8 16 32 |
Проверьте, является ли число простым.
Вводится одно натуральное число n не превышающее 2000000000 и не равное 1.
Необходимо вывести строку prime, если число простое, или composite, если число составное.
| Ввод | Вывод |
|---|---|
5 |
prime |
Дано натуральное число \(N>1\). Выведите все его простые натуральные делители с учетом кратности. Алго ритм должен иметь сложность \(O(\sqrt{n})\).
Вводится натуральное число \(N \le 2 * 10^9\).
Выведите ответ на задачу.
| Ввод | Вывод |
|---|---|
12 |
2 2 3 |
Вывести все простые числа от \(M\) до \(N\) включительно.
В первой строке находятся разделённые пробелом \(M\) и \(N\). 2 <= \(M\) <= \(N\) <= 300 000.
Вывести числа в порядке возрастания, по одному в строке. Если между \(M\) и \(N\) включительно нет простых - вывести "Absent".
| Ввод | Вывод |
|---|---|
2 5 |
2 3 5 |
4 4 |
Absent |
Cоздайте массив [True] * (\(K\) + 1). Заполните его значениями так, чтобы IsPrime[i] == True, если i — простое число и IsPrime[i] == False, если i — составное.
Для этого сначала заполняем массив True. Затем “вычеркиваем” (то есть помечаем нулями) те элементы, которые делятся на 2, начиная с 4. Затем вычеркиваем те элементы, которые делятся на 3, начиная с 9. Затем вычеркиваем элементы, которые делятся на 5, начиная с 25...
И так далее — находим следующее невычеркнутое число \(p\) и вычеркиваем все кратные \(p\) начиная с \(p^2\). В результате невычернутыми останутся только простые числа.
Такая процедура называется “Решето Эратосфена”.
Напишите программу, которая строит решето Эратосфена, потом считывает натуральное число \(N\) и выводит \(N\)-е по счету простое число. Гарантируется, что это число не превосходит \(N \le 100000\). Обратите внимание на то, что 100000-е простое число не является числом 100000.
Выведите ответ на задачу.
| Ввод | Вывод |
|---|---|
5 |
11 |
Вывести все простые числа от \(M\) до \(N\) включительно.
В первой строке находятся разделённые пробелом \(M\) и \(N\). 2 <= \(M\) <= \(N\) <= 1 000 000.
Вывести числа в порядке возрастания, по одному в строке. Если между \(M\) и \(N\) включительно нет простых - вывести "Absent".
| Ввод | Вывод |
|---|---|
2 5 |
2 3 5 |
4 4 |
Absent |
Программист на Северном полюсе работал за компьютером в варежках и поэтому мог набирать только 0 и 1, а клавиша 0 запала. Сможет ли он набрать число, состоящее только из единиц и при этом кратное заданному N?
Программе дано число N (1 ≤ N ≤ 106).
Вывести минимальное число, удволетворяющее требованию, или "NO" , если такого числа не существует.
| Ввод | Вывод |
|---|---|
100 |
NO |
57 |
111111111111111111 |
Даны два натуральных числа \(A\) и \(B\) (2 \(\le\) \(A\), \(B\) \(\le\) 2 * 1012). Найдите такое минимальное натуральное \(n\), что \(B^n\) делится на \(A\).
Программа получает на вход два числа \(A\) и \(B\).
Программа выводит одно значение \(n\). Если никакая степень числа \(B\) не делится на \(A\), то выведите число -1.
| Ввод | Вывод |
|---|---|
54 60 |
3 |
Два различных числа \(n\) и \(m\) называются дружественными, если сумма делителей числа \(n\) (включая 1, но исключая само \(n\)) равна числу \(m\) и наоборот. Например, 220 и 284 – дружественные числа.
Дано число \(k \le 50000\)
Выведите все пары дружественных чисел, каждое из которых не превосходит \(k\). Пары необходимо выводить по одной в строке, разделяя числа в паре пробелом. Каждая пара должна быть выведена только один раз (перестановка чисел новую пару не дает).
| Ввод | Вывод |
|---|---|
300 |
220 284 |