Поиск ближайшего делителя

Задача. Даны два числа s и p, при этом s <= p. Требуется найти ближайший после s делитель d числа p, такой что:
s <= d p mod d = 0 если s != d, то p mod (s,d] != 0 // в дипазоне от s до d нет делителей
Например, для s = 7 и p = 33, d = 11
Придумал два вот таких варианта:
// тупой перебор int delimeter_1(int s, int p) { if(s <= p) { int d = s; while(0 != p % d) { ++d; } return d; } return p; }
// перебор поумнее int delimeter_2(int s, int p) { if(s <= p) { int q = p / s; while(0 != p % q) { --q; } return p / q; } return p; }
Пояснение. Например для числа 15 построим таблицу:
делители: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 частное : 15 7 5 3 3 2 2 1 1 1 1 1 1 1 1 остаток : 0 1 0 3 0 3 1 7 6 5 4 3 2 1 0
Так вот, в delimeter_1 мы движемся по строке делители, а в delimeter_2 по строке частное - второй вариант получается чуть быстрее.
У меня есть подозрение, что возможно есть более быстрое и элегантное решение, основанное на свойствах чисел, либо вообще без циклов, либо с более короткими циклами. Мне не обязательно готовое решение, может кто-то подскажет где почитать на близкую тему или выскажит интресные мысли и замечания.
Подумав, пришел к выводу, что аналитического неитерационного алгоритма не сущетсвует. Такой алгоритм можно представить в виде некой функции f(q,s) = d, то есть q mod f(q,s) = 0, или в виде уравнения q mod (s + k) = 0, где s + k = d. Как вытащить k мне не известно, перешерстил все и ничего не нашел.

Ответ

Решая перебором, следует комбинировать оба подхода. Для p/d < d применять первый, для p/d > d второй. Т.е. сначала бежим по делителям, потом по частным. В случае с таблицей по 15 будет от 1 до 4 (по делителю) первый подход, от 3 до 1 (по частным) второй.
Для варианта d = 1000 таблица будет из 1000 столбцов, а итераций от 1 до 31 и обратно от 31 до 1 всего 62 (плюс-минус) максимум.
Дальше учитываем s и оптимизируем. Т.к. для первого подхода мы пройдем все делители от s до sqrt(p) второй раз при проходе по частным эти делители проходить не нужно, второй подход можно сразу начинать с s и до 1. Получаем простой цикл от 1 до sqrt(p), просто для выявления ближайшего к s делителя порядок не прямой.
В итоге:
int delimeter_3(int s, int p) { int i = s; while(i > 1) { if(p % i==0) break; if(i >= s) i++ else i--; if(i > sqrt(p)) i = min(s, p / s) - 1; }
return i >= s ? i : i ? p / i : p; }