Пояснення:В качестве кандидатов нужно рассматривать числа, не превышающие
(
S
−
1
)
2
, так как в худшем случае составное число вида
x
будет иметь два наибольших делителя
и 1. Время работы этого алгоритма
O
4
. Можно существенно ускорить вычисления, если учесть, что при поиске разложения на множители числа
N
можно рассмотреть только числа не превышающие
√
. Наибольшим делителем числа
будет
a
, где
– наименьший делитель, а вторым наибольшим делителем будет либо
b
– второй по величине делитель
(также либо число, либо
), либо
, если
является произведением двух различных чисел, либо 1, если
=
.
Пояснення:В качестве кандидатов нужно рассматривать числа, не превышающие
(
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
.
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
const int n = 5;
double a[n][n];
double m1, m2;
srand(time(0));
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
a[i][j]=-20 + (101.0 / RAND_MAX) * rand();
cout << fixed << setw (7) << setprecision (2) << a[i][j];
}
cout <<endl;
}
m1=a[0][0];
m2=a[0][n-1];
for (int i = 1; i < n; i++){
if (a[i][i]>m1) m1=a[i][i];
if (a[i][n-i-1]>m2) m2=a[i][n-i-1];
}
cout << "m1=" << m1 << " m2=" << m2 << endl;
}
37.11 71.19 25.77 53.53 35.74
39.90 63.69 11.67 70.38 -4.10
64.46 52.37 35.03 42.58 69.18
44.22 8.46 13.23 71.17 3.10
6.83 65.07 75.24 21.61 37.22
m1=71.17 m2=70.38