РЕШУ ЕГЭ — информатика

Задания

Пусть M  — сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то считаем значение M равным нулю.

Напишите программу, которая перебирает целые числа, большие 452 021, в порядке возрастания и ищет среди них такие, для которых значение M при делении на 7 даёт в остатке 3. Вывести первые 5 найденных чисел и соответствующие им значения M.

Формат вывода: для каждого из 5 таких найденных чисел в отдельной строке сначала выводится само число, затем  — значение М. Строки выводятся в порядке возрастания найденных чисел.

Например, для числа 20 М  =  2 + 10  =  12, остаток при делении на 7 не равен 3; для числа 21 М  =  3 + 7  =  10, остаток при делении на 7 равен 3.

Количество строк в таблице для ответа избыточно.

Ответ:

Решение. Заметим, что у каждого числа делители парные, например у числа 8 это 1 и 8, 2 и 4. Будем находить первый натуральный делитель числа, отличный от единицы, и проверять, делится ли сумма найденного делителя с его парным делителем на 7 с остатком 3. Если условие выполняется  — выводим исходное число и сумму его парных минимального и максимального делителей на экран и выходим из цикла для перебора делителей числа, иначе сразу выходим из цикла для перебора делителей числа.

Приведём решение на языке Pascal.

var
    count, j, k, sqrtI, num: longint;
begin
    num := 452022;
    count := 0;
    while True do begin
        sqrtI := round(sqrt(num));
        for j := 2 to sqrtI do begin
            if num mod j = 0 then begin
               if (j + num div j) mod 7 = 3 then begin
                  count := count + 1;
                  writeln(num, ' ', j + num div j);
                  break;
               end
               else break;
            end;
        end;
        if count = 5 then break;
        num := num + 1;
    end;
end.

В результате работы программа должна вывести следующее:

452025 150678

452029 23810

452034 226019

452048 226026

452062 226033

Приведём решение на языке Python.

num = 452022

count = 0

while True:

sqrtI = round(num ** 0.5)

for j in range(2, sqrtI + 1):

if num % j == 0:

if (j + num // j) % 7 == 3:

count += 1

print(num, ' ', j + num // j);

break

else:

break

if count == 5:

break

num += 1

Приведём решение Ивана Гладких на языке Python.

c = 0

for n in range(452022, 1000000):

de = []

for j in range(2,n):

if n % j == 0:

de.append(j)

if len(de) >= 2:

m = de[0] + de[-1]

if m % 7 == 3:

c += 1

print(n , m)

if c == 5:

break

№ п/п	№ задания	Ответ
1	36038	452025 150678 452029 23810 452034 226019 452048 226026 452062 226033

Ключ