Какое-то время я посвятил играм с простыми числами. В студенчестве еще.
Вот тут не надо каждый раз прибавлять единичку.
if (K % (i + 1) == 0) {
Ее просто надо учесть в условиях цикла.
if (K % i == 0) {
Далее. Если нужно найти первый попавшийся делитель - то не надо перебирать все числа. Достаточно только 2 и все нечетные. Или даже лучше задать хард-кодом таблицу простых чисел до 2^16. Это как раз будет половина разрядной сетки int32.
int primes[] = { 2,3,5,7,11,13,17...... 65521 }
Это даст хорошее ускорение для поиска. Хотя время загрузки executable может увеличится. Кстати у меня много вопросов к бенчмаркам где стоит запредельно короткое время инициализации (0.25 s). Здесь - практически невозможно вычленить где время занимает алгоритм а где - просто запуск процесса операционки. Обычно когда меряют что-то подобное - меряют длительные процессы хотя-бы порядка минут но никак не секунд.