// PascalABC.NET 3.1, сборка 1230 от 27.04.2016 begin var n:=ReadInteger('n='); var a:=MatrixRandom(n,n,10,99); var s:=0; var k:=0; for var i:=0 to n-1 do begin for var j:=0 to n-1 do Print(a[i,j]); Writeln; if a[i,i].IsEven then begin s+=a[i,i]; Inc(k) end; end; if k>0 then Writeln('S=',s/k:0:2) else Writeln('На главной диагонали нет четных элементов') end.
Пояснення:В качестве кандидатов нужно рассматривать числа, не превышающие
(
S
−
1
)
2
, так как в худшем случае составное число вида
x
2
будет иметь два наибольших делителя
x
и 1. Время работы этого алгоритма
O
(
S
4
)
. Можно существенно ускорить вычисления, если учесть, что при поиске разложения на множители числа
N
можно рассмотреть только числа не превышающие
√
N
. Наибольшим делителем числа
N
будет
N
a
, где
a
– наименьший делитель, а вторым наибольшим делителем будет либо
N
b
, где
b
– второй по величине делитель
N
(также либо число, либо
a
2
), либо
a
, если
N
является произведением двух различных чисел, либо 1, если
N
=
a
2
.
begin
var n:=ReadInteger('n=');
var a:=MatrixRandom(n,n,10,99);
var s:=0;
var k:=0;
for var i:=0 to n-1 do begin
for var j:=0 to n-1 do Print(a[i,j]);
Writeln;
if a[i,i].IsEven then begin s+=a[i,i]; Inc(k) end;
end;
if k>0 then Writeln('S=',s/k:0:2)
else Writeln('На главной диагонали нет четных элементов')
end.
Тестовое решение
n= 8
63 13 33 90 25 21 87 91
88 88 48 13 30 59 81 27
73 23 76 77 52 19 33 97
53 87 13 74 17 35 61 70
77 96 51 61 82 33 63 22
39 88 84 54 88 73 74 69
76 26 69 14 45 80 70 54
80 36 47 38 18 22 84 62
S=75.33