Разбор задачи № 25 демо-варианта 2022 года
Пусть M – сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то значение M считается равным нулю.
Напишите программу, которая перебирает целые числа, большие 700 000, в порядке возрастания и ищет среди них такие, для которых значение M оканчивается на 8. Выведите первые пять найденных чисел
и соответствующие им значения M.
Формат вывода: для каждого из пяти таких найденных чисел в отдельной строке сначала выводится само число, затем – значение M. Строки выводятся в порядке возрастания найденных чисел.
Решение
1. Как вывести только 5 найденных чисел? Для этого организуем цикл, который будет уменьшать значение переменной (
N) от 5 до 0. Как только
N станет равной
0, цикл заканчивает свою работу.
Внутри цикла будем перебирать все числа большие 700 000 (используя для этого переменную
i) и вычислять значение
M, и если оно будет оканчиваться на
8, то будем выводить это число и его значение
M, а также уменьшать счетчик выведенных чисел (
N). Найденные числа будет выводиться в порядке возрастания, так как каждое следующее рассматриваемое число на 1 больше предыдущего.
|
C++
|
Python |
Pascal |
i = 700000
N = 5
while (N != 0)
{
i++;
...
if (M % 10 == 8)
{
вывод
N--;
}
}
|
i = 700 000
N = 5
while N != 0:
i += 1
...
if (нашли нужное число)
вывод
N = N - 1
|
i := 700000
N := 5
while N != 0 do
begin
i := i + 1
...
if нашли нужное число then
begin
вывод
N := N - 1;
end;
end;
|
2. Как посчитать значение
M?
Заметим, что минимальный и максимальный делители числа (
i) являются "симметричными" (парными). Поэтому нам достаточно найти первый отличный от 1 делитель. Он и будем минимальным. Максимальный делитель можно будет найти, разделив число (
i) на его минимальный делитель. Сразу же вычислим значение
M для числа (
i). Для каждого числа
i значение
M считается свое, поэтому перед циклом необходимо
M обнулить.
|
C++
|
Python |
Pascal |
M = 0
while (del * del < i)
{
if (i % del == 0)
{
M = del + i/del;
break;
}
del++;
}
|
M = 0
while del * del < i:
if i % del == 0:
M = del + i/del
break
del++
|
M := 0
while del * del < n do
begin
if n mod i = 0 then
begin
M := del + i div del:
break;
end;
del := del + 1;
end;
|
Возможные делители перебираем от 2 до
\(\sqrt n - 1\). Так как, если число (
i) является полным квадратом и не имеет других делителей, кроме
\(\sqrt n\), то в данном случае
M у нас должно быть равным
0.
Если мы нашли не равный 1 минимальный делитель, то можно прерывать (
break) цикл
while. Дальше перебирать возможные делители не имеет смысла.
Попробуйте написать программу целиком самостоятельно.