Задача. Даны два числа 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
мне не известно, перешерстил все и ничего не нашел.
int d = s + 1;
в тупом иint q = p / s - 1;
в более умном варианте. – avp 8 июл '15 в 9:39s
по условию задачи. – Vesper 8 июл '15 в 9:49s
??? Там ведь прямо написано -- "найти ближайший после s делитель" – avp 8 июл '15 в 10:25s <= d
истина, если s=d. – Vesper 8 июл '15 в 10:43