Есть интервал, пределы которого могут быть очень большими. Дано целое число. Задание: определить множители этого числа на интервале.
В принципе сразу же что пришло в голову это простой перебор чисел, по принципу каждый з каждым, но стоит ограничение времени в одну секунду.
Моя попытка:
Берем интервал чисел, а именно нам нужно два числа, это конец интервала и его начало.
Дальше мы умножаем эти два числа, и проверяем полученный результат с условием: Если число, которое мы получили, меньше, чем число которое нам нужно разложить на множители, то continue, после чего увеличиваем минимальное число на единицу;
Если же, число которое мы получили больше того числа, которое нам нужно разложить, то:
- Мы отнимаем от числа, которое мы получили, число которое нам нужно разложить.
- Мы, это число которое получили после отнимания делим на начальное число(которое идет вверх интервала от минимальной цифры). После чего, проверяем условие: Если получается число, не целого типа, то множителей не будет, а следовательно мы увеличиваем начальное значение на единицу и continue;
- Если же, число которое мы получили при делении, целого типа, тогда мы: Это число, отнимаем от максимального и умножаем на начальное число, в следствии чего мы получаем два множителя нужного числа.
Пример:
Есть интервал чисел от 14 к 28, и число которое мы хотим разложить на множители, пусть будет 450.
Для начала нам нужно два числа, это максимальный и минимальный элемент интервала, в данном случаи это 14 и 28.
Дальше мы умножаем эти два числа, получаем результат: 14*28 = 392.
Число, которое мы получили, есть меньше чем число, которое нам нужно разложить на множители, то есть 450, тогда мы увеличиваем 14 на единицу, и начинаем все с начала.
- 392 < 450, => Не подойдет!
- Продолжаем: 15(14+1) * 28 = 420 < 450 => Не подойдет!
- 16(15+1) * 28 = 448 < 450 => Не подойдет!
- 17(16+1) * 28 = 476 > 450, тогда:
Мы от числа, которое получили, то есть 476 отнимаем число 450, получаем результат: 26. После этого, мы 26 делим на число 17 в последствии чего получаем число не целого типу, значит нам такой расклад не подойдет, мы к 17 додаем единицу и продолжаем поиск.
18(17+1) * 28 = 504. 504 - 450 = 54/18 = 3. В данном случае деление прошло успешно, значит мы уже нашли первые множители, теперь нам нужно точно их определить, для этого мы от максимального числа, то есть 28 отнимаем число которое мы получили при делении(3) = 28-3 = 25. В результате чего мы получаем два числа: Это 18 и 25, проверяем: 18*25 = 450.
По такому принципу работает мой алгоритм, но проблема моя вот в чем, как я могу этот алгоритм перенести на случай, когда нам дано два интервала, то есть например: 14 к 28 и 12 к 32, он вроде бы и определяет множители, но выходит за пределы второго интервала, благодарен за потраченное время, к языку программирования не привязан, буду благодарен за помощь в любом виде.