С2. Задания для самостоятельной работы

• Алгоритмы над целыми числами

Задание 1. Найти разложение на простые сомножители числа 100! (факториал).

Указания:

а) Факториалом натурального числа $N$ (обозначается $N!$) называется произведение всех целых чисел от 1 до $N$.

б) Математические рассуждения приводят к следующему выводу: простое число $p$ является делителем числа $n!$ с кратностью $k$, определяемым по формуле:

$$k={\left[{{n}\over{p^1}}\right]}+{\left[{{n}\over{p^2}}\right]}+...= \sum\limits_{k>0}{\left[{{n}\over{p^k}}\right]}$$

где символ $[ ]$ означает целая часть числа

Задание 2. Найти совершенные числа, не превосходящие $N$.

Совершенным называется число, равное сумме своих правильных делителей, то есть делителей, меньших самого числа. Числа 6 и 28, например, являются совершенными ($6=1+2+3$ и $28=1+2+4+7+14$).

Указание: Использовать принцип решета Эратосфена, накапливая в каждом элементе массива сумму всех делителей числа, являющегося индексом данного элемента.

Задание 3. Найти и вывести все числа-близнецы из промежутка $[N, M]$.

Указание: Числами-близнецами называются два простых нечетных числа, разнящихся на 2 (например: 11 и 13, 59 и 61 и т.д.)

Задание 4. «Палиндромы». Определить количество простых чисел, не превосходящих заданное число $N$ $(N \lt 16000)$, шестнадцатеричная форма записи которых является палиндромом, то есть перевертышем.

Указание. В десятичной системе счисления для $N=20$ простых чисел восемь: 2, 3, 5, 7, 11, 13, 17, 19. Но в 16-ричной системе счисления чисел-палиндромов семь: 2, 3, 5, 7, B, D, 11.

Задание 5. Разбить число на сумму двух простых чисел.

Задание 6. «Скатерть Улама». Если против часовой стрелки по спирали, начиная с центра экрана, выписывать подряд натуральные числа, заменяя простые числа звездочками, а составные – пробелами, то получится узор, называемый скатертью Улама (Станислав Улам – математик). Написать программу, рисующую скатерть Улама на экране.