Analysis of problem #25 of the 2022 demo
Let M
– the sum of the minimum and maximum natural divisors of an integer, not counting one and the number itself. If the number does not have such divisors, then the M
value is considered equal to zero.
Write a program that iterates over integers greater than 700 000
, in ascending order and looks for those for which M
ends in 8
code>. Print the first five found numbers
and their corresponding M
.
values
Output format: for each of the five such found numbers in a separate line, the number itself is displayed first, then – M
value. Strings are displayed in ascending order of found numbers.
Solution
1. How to display only 5 found numbers? To do this, we will organize a loop that will decrease the value of the variable (
N
) from 5 to 0. As soon as
N
becomes equal to
0
, the loop  ;finishes its work.
Inside the loop, we will iterate over all numbers greater than 700,000 (using the
i
variable for this) and calculate the value
M
, and if it ends in
8
, then we will display this number and its value
M
, and also decrement the counter of output numbers (
N
). The found numbers will be displayed in ascending order, since each next considered number is 1 more than the previous one.
C++
|
Python |
Pascal |
i = 700000
N=5
while (N != 0)
{
i++;
...
if (M % 10 == 8)
{
conclusion
N--;
}
}
|
i = 700,000
N=5
while N != 0:
i += 1
...
if (found the right number)
conclusion
N = N - 1
|
i := 700000
N := 5
while N != 0 do
begin
i := i + 1
...
if found the right number then
begin
conclusion
N := N - 1;
end;
end;
|
2. How to calculate the value of
M
?
Note that the minimum and maximum divisors of a number (
i
) are "symmetrical"; (in pairs). Therefore, it is enough for us to find the first divisor different from 1. It will be minimal. The maximum divisor can be found by dividing the number (
i
) by its minimum divisor. Let's immediately calculate the
M
value for the number (
i
). For each number
i
the
M
value is considered to be different, so
M
must be set to zero before the loop.
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;
|
We iterate over possible divisors from 2 to
\(\sqrt n - 1\). Since if a number (
i
) is a perfect square and has no other divisors than
\(\sqrt n\), then in this case,
M
should be equal to
0
.
If we have found a minimum divisor that is not equal to 1, then we can break (
break
) the
while
loop. It makes no sense to sort through possible divisors.
Try writing the entire program yourself.