0
$\begingroup$

I need to factorize a number starting from an initial divisor and going down by $1$ at each step. For example, starting from $99$ and decreasing it one by one

$$9779 = 99 \times 98 + 77$$ $$9779 = 98 \times 99 + 77$$ $$9779 = 97 \times 100 + 79$$ $$\vdots$$ $$9779 = 77 \times 127 + 0$$

I reach the zero remainder after $23$ steps.

I was wondering if there is a clever way to "predict" the first null remainder given the first division(s). I saw this question but mine has a particular pattern so maybe there is a better solution than brute force.

Thanks a lot

$\endgroup$
7
  • 1
    $\begingroup$ Well, you can certainly jump two each time if looking for factors of an odd number as they'll never be even $\endgroup$ Dec 23, 2019 at 16:25
  • 2
    $\begingroup$ Aren't you just asking for the largest divisor of the number less than 100? $\endgroup$
    – Calvin Lin
    Dec 23, 2019 at 16:26
  • $\begingroup$ You could do trial division by only using the primes. If you have completed the factorization, you can easily find all divisors. Knowing that $1001$ is divisible by $7$ and $11$ here gives immediately two prime divisors. $\endgroup$
    – Peter
    Dec 23, 2019 at 16:26
  • 1
    $\begingroup$ In the end , it simply depends upon the number you choose as the starting value . If you would have started at $150$ , it would take you $24$ steps to reach to the first divisor , i.e $127.$ $\endgroup$ Dec 23, 2019 at 16:27
  • 1
    $\begingroup$ Why do you start with 99? $\endgroup$
    – miracle173
    Dec 23, 2019 at 16:29

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.