Как можно ускорить алгоритм?
Вы правильно поняли, что вам надо найти минимальный делитель числа K.

Проблема в том, что если число K простое - то вы будете проходиться до него. Есть трюк - достаточно проверять только числа до корня из K. Ведь если у числа есть какой-то минимальный собственный (меньше него самого) делитель, то он точно меньше корня (потому что делителей как минимум два, и если минимальный из них больше корня, то их произведение - больше самого числа).

Если вы не нашли делителя до корня, то число простое и в качестве делитеял можно брать все K и тогда ответ будет K-1.
Первый игрок назначает например число три (K). Второй назначает число 2 (L=K-1), и всегда забирает последнюю пуговицу. Что-то явно не то с условиями задачи.