#алгоритм #математика #числа
Задача. Даны два числа 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 мне не известно,
перешерстил все и ничего не нашел.
Ответы
Ответ 1
Решая перебором, следует комбинировать оба подхода. Для 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;
}
Ответ 2
Очевиден тот факт, что в случае нулевого остатка операция деления даёт сразу пару
делителей числа p (делитель и частное), причём половина делителей лежит слева от числа
q=[sqrt(p)], а половина - справа. При больших p неизбежно q << p, и части
(q и p-q) явно неравны, поэтому, к примеру, при факторизации стараются начинать с
меньших делителей.
Заметим, что при исходных данных (s=3, p=94) нахождение требуемого искомого делителя
"в лоб" потребует 91 операцию перебора, в то время как факторизация - всего лишь одну.
Причина кроется в низкой эффективности поиска делителей на интервале (q,p), потому
что их плотность там мала, а требуемый делитель 2 (который является ключом к частному
47) мы проскочили.
Т.е. в случае s < q есть риск превратить поиск делителя в рулетку.
Другое дело, если s>>q. Перебирая (в обратном порядке) частные от деления p на
t, t-1,...,2, где t = [q/s], мы повышаем шансы найти требуемый делитель. Т.е. в этом
случае параметр s может принести пользу.
Но что же делать при s < q? В этом случае остаётся выбор - пойти на факторизацию
или ограничиться проверкой делителей. Во втором случае можно начать с перебора делителей
по возрастанию, начиная с s+1, но перебор на интервале [q,p/s) вести с помошью таблицы
неиспользованных частных (в обратном порядке), а на интервале [p/s,p) -- непосредственно
вычисляя оставшиеся частные делением p на s, s-1, ....
Ответ 3
Вначале надо факторизовать число, потом построить список его делителей, отсортировать
его по возрастанию и найти, в какое место попадает s, и взять следующий справа делитель.
Факторизовать чем-нибудь отсюда, дальше проще. А перебирать задолбаешься на первом
же Р больше миллиона.
