Конечно же, тут не надо вычислять факториал и проверять его делимость
надо разложить делитель на простые множители. посмотреть степени этих множителей. от этого строить искомое число.
например, если у нас число 18. Это 2 * 3^2. здесь ответ будет 6 (6! делится на 18). а почему? да потому, что в произведении 1*2*3*4*5*6 встретится и двойка, и обе тройки (в числах 3 и 6). В общем, как-то так.
другое дело, насколько это будет быстро. Оную операцию надо проделать 100000 раз. Раскладывание на простые множители - не такая простая вещь. Потому тут надо что-то ещё думать.