Пояснення:В качестве кандидатов нужно рассматривать числа, не превышающие
(
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
.
x1 x2 x3 x4 x2∧x4 ¬x1 ¬x1∨x3 x2∧x4∧(¬x1∨x3) ¬x2∧x4∧(¬x1∨x3) ¬x1∧x2 ¬x3 ¬x1∧x2∧¬x3 x4∨¬x1∧x2∧¬x3 ¬x2∧x4∧(¬x1∨x3)∧(x4∨¬x1∧x2∧¬x3) x1∧x2 ¬x1∧x2 ¬x2∧x4∧(¬x1∨x3)∧(x4∨¬x1∧x2∧¬x3)∧¬x1∧x2 ¬x2∧x4∧(¬x1∨x3)∧(x4∨¬x1∧x2∧¬x3)∧¬x1∧x2≡1
0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 0
0 0 0 1 0 1 1 0 1 0 1 0 1 1 0 1 1 1
0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0
0 0 1 1 0 1 1 0 1 0 0 0 1 1 0 1 1 1
0 1 0 0 0 1 1 0 1 1 1 1 1 1 0 1 1 1
0 1 0 1 1 1 1 1 0 1 1 1 1 0 0 1 0 0
0 1 1 0 0 1 1 0 1 1 0 0 0 0 0 1 0 0
0 1 1 1 1 1 1 1 0 1 0 0 1 0 0 1 0 0
1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0
1 0 0 1 0 0 0 0 1 0 1 0 1 1 0 1 1 1
1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0
1 0 1 1 0 0 1 0 1 0 0 0 1 1 0 1 1 1
1 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0
1 1 0 1 1 0 0 0 1 0 1 0 1 1 1 0 0 0
1 1 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0
1 1 1 1 1 0 1 1 0 0 0 0 1 0 1 0 0 0
Объяснение:
вроде так