472A — Уроки дизайна задач: учимся у математики

Revision ru1, by tempdefaultdef, 2022-01-28 09:25:36

Число у которого количество делителей больше двух называется составным. Даётся целое число N > 11.Для решения задачи можно сделать следующее: — Если число чётное: Все чётные числа (больше 2) составные, так как у них есть минимум 3 делителя (1, 2 и само число). 4 составное число. Так как N > 11 и N чётное число, N будет составным и если вычесть из него 4, получится составное число. Таким образом можно представить N в виде суммы двух составных чисел 4 и N — 4; — Если число нечётное: Теперь воспользуемся составным числом 9 (делители 1, 3, 9). Минимальное значение которое N может принять, это 13 — 9 = 4 которое тоже является составным. Следовательно можно сказать, что если из нечётного числа (большее 12) вычесть 9, получится составное число. Таким образом можно представить N в виде двух составных чисел 9 и N — 9;

Сложность алгоритма: О(1)

Tags 472a, уроки дизайна задач, математика, теория чисел, 800, креатив

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru1 Russian tempdefaultdef 2022-01-28 09:25:36 953 Первая редакция (опубликовано)