There is an interval whose limits can be very large. Given an integer. Task: to determine the multipliers of this number on the interval.

In principle, immediately it occurred to me that this is a simple enumeration of numbers, according to the principle of each and every one, but the time limit is one second.

My attempt:

We take the interval of numbers, namely, we need two numbers, this is the end of the interval and its beginning.
Then we multiply these two numbers, and check the result obtained with the condition: If the number we received is less than the number that we need to factor into, then continue, and then increase the minimum number by one;

If, however, the number we received is larger than the number we need to expand, then:

  1. We subtract from the number we received, the number we need to expand.
  2. We, this number which we received after weaning, divide by the initial number (which goes up the interval from the minimum digit). After that, we check the condition: If a number is obtained that is not of integer type, then there will be no multipliers, and therefore we increase the initial value by one and continue;
  3. If, on the other hand, the number we got from dividing is of integer type, then we: This number is subtracted from the maximum and multiplied by the initial number, in consequence of which we get two multipliers of the desired number.

Example:

There is an interval of numbers from 14 to 28, and the number we want to factor into, let it be 450.
First we need two numbers, this is the maximum and minimum element of the interval, in this case it is 14 and 28.
Then we multiply these two numbers, we get the result: 14 * 28 = 392. The number we received is less than the number that we need to factor into, that is, 450, then we increase 14 by one, and we start from the beginning .

  1. 392 <450, => Not suitable!
  2. We continue: 15 (14 + 1) * 28 = 420 <450 => It will not work!
  3. 16 (15 + 1) * 28 = 448 <450 => Not suitable!
  4. 17 (16 + 1) * 28 = 476> 450, then:

We get the result from the number we received, that is, 476 subtract the number 450, we get the result: 26. After that, we divide 26 by 17 and then we get the number not of integer type, it means that this alignment doesn’t work for us, we finish by 17 and continue searching.

18 (17 + 1) * 28 = 504. 504 - 450 = 54/18 = 3. In this case, the division was successful, which means we have already found the first factors, now we need to determine them exactly, for this we are from the maximum number, there are 28 subtracting the number that we got when dividing (3) = 28-3 = 25. As a result, we get two numbers: These are 18 and 25, and we check: 18 * 25 = 450.

According to this principle, my algorithm works, but my problem is how I can transfer this algorithm to the case when we are given two intervals, that is, for example: 14 to 28 and 12 to 32, it seems to determine the multipliers, but it turns out beyond the second interval, grateful for the time spent, is not tied to a programming language, I will be grateful for help in any way.

  • The essence of the algorithm is that it performs much fewer actions compared to simply iterating through numbers, for example, in the same interval 14-28, we perform 15 actions (according to this algorithm), but if we simply iterate, we would do approximately 91 tests. And of course this algorithm is more interesting, I basically do such tasks for the sake of new ideas, I think this is a pretty good idea, you can basically drop me to the ground =) - Andrey Nikolishin
  • 2
    We perform factorization on prime factors and see which variants of the factors fit into the range? .. For really large ranges, faster than sorting the factors. - Harry
  • Damn, it's still dividers. The mess we have with the terminology ... - Alexey Ten
  • Perhaps =) I have a paradox mainly in the scientific process. Basically, everyone teaches math and thus becomes closer to programming and logic. I have everything in the reverse order, I didn’t study math from the word at all, but I started programming quite well, and thus I get closer to mathematics, so maybe some kind of inaccuracy will be exactly with the terminology, I apologize. - Andrey Nikolishin

1 answer 1

I do not quite understand whether you are looking for multipliers on a range or decomposition on 2 multipliers on a range. In any, your algorithm runs per line on the length of the range. Dumb search also works beyond the line of the range length, while the constant is much smaller. As you managed in the search from 14 to 28 to do 91 test, I will not put my mind to it. In my math 28 - 14 = 14

  • This is clearly not an answer, but a comment - MBo
  • Two factors on a certain interval. Well, with a simple enumeration of numbers, on the principle of each s each, 14 from 14-28, 15 from 14-28, 16 from 14-28, there will be even more, since we multiply each number with an interval. - Andrey Nikolishin
  • one
    Why go through all the pairs? It is enough for each of the numbers in the interval 1 time to check whether it is divisible by the initial number. And if divided, whether the result is in the interval. If you need to decompose into 2 multipliers, you can check whether the root is in the interval, and if it enters to go from minimum to root. If not included - no answer. - Dmitry Zinenko
  • Well, in that case, yes, you will need to try, thanks for that. - Andrey Nikolishin