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

#алгоритм #математика #числа

Задача. Даны два числа 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, и взять следующий справа делитель.
Факторизовать чем-нибудь отсюда, дальше проще. А перебирать задолбаешься на первом
же Р больше миллиона.