Да, говорит, двузначные надо знать. С трёхзначными решил наоборот по сравнению с твоим решением - т.е. искал n в квадрате, максимально приближенное к нужному числу, но больше него. А потом проверял делимость на все простые от 1 до n, при том, что признаки делимости на 2, 3, 5, 7, 11 они знают.