Делимость n! на n^2 C++

Ладно, попытаюсь изложить, почему почти (с одним исключением) прав Юрий Козлов.

Итак, нам нужно, как я уже писал, проверить делимость (n-1)! на n. Очевидно, что если это число простое, то среди сомножителей (n-1)! его не будет, и делиться (n-1)! на n не будет.

Осталось разобраться с составными.

Любое составное число представимо в виде

произведения простых чисел в каких-то степенях. Если в этом разложении есть хотя бы два простых числа, то, во-первых, у них нет общих делителей, а во-вторых, каждый сомножитель строго меньше n, так все сомножители входят в (n-1)!, а значит, делимость обеспечена.

Осталось рассмотреть случай, когда

Случай k = 1 соответствует простому числу и уже рассмотрен. Для делимости (n-1)! на p^k требуется, чтобы p как минимум k раз входило в (n-1)!, т.е. выполнялось условие pk < n, или pk < p^k, или p^k-1 > k при k >= 2 (единицу мы уже с негодованием отвергли :)) Методом матиндукции очень легко показать, что для любого p > 1 если p^k-1 > k, то для k+1 это справедливо и подавно. Главное - чтоб выполнялось начальное условие. А не выполняется оно для k==2 только для одного числа - p==2. Но уже для p==2 и k==3 все работает, и матиндукция справедлива. Таким образом,

(n-1)! не делится на n только для n простых и для n==4.

Соответственно, то же справедливо и для n! и n².

Так что на C++ надо реализовать проверку на простоту и на равенство 4...