SPyofgame's blog

Closest Divisor of given number problems
By SPyofgame, history, 4 years ago, In English

Question: Given two positive numbers N and M, find minimal |c — M| where N mod c = 0

Can we solve this problem in O(log (n)) or faster ?

Here is my approach in O(sqrt(n))

My code

Sorry for my bad English ;-;

If I have wrong something, please tell me. It is better to do that than just downvote me because I and someone will learn many new things <3

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

If you preprocess divisors for all numbers ( reference: code $$$O(NlogN)$$$ ), then you have vector $$$divisors[N]$$$, and you can binary search for $$$M$$$ in that vector ( even iterating through the array is good enough, because there are very few divisors link ).

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks <3

    But if there is just one query, can I approach faster than O(√(n)) ?

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why I cant see your ideone code ?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Weird. It should be visible.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you show me the source code or pseudo code ?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +2 Vote: I do not like it
          Code
          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            oh, ok thanks <3

            We can use this as sieve right ?

            Sieve
            → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +12 Vote: I do not like it

If I pick $$$M = \lfloor N/2 \rfloor$$$, finding such a $$$c$$$ is equivalent to finding a non-trivial divisor, so your problem is at least as hard as factoring.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Wouldn't it be "at least as hard as factoring"? Or is the answer somehow obvious if you have the factoring (I can't see why it is)?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Right, 'reduces to factoring' would be a better way to phrase it.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry but I dont understand what is non-trivial divisor meaning. Is that mean I cant use the O(√(n)) approach ?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      You can use the $$$O(\sqrt{n})$$$ approach, I'm saying you can't (hope to) do better than that, since solving your problem in $$$O(\log n)$$$ time means solving prime factorization in that time.

      By 'non-trivial divisor' of $$$N$$$ I mean any divisor that is not $$$1$$$ or $$$N$$$ itself. It should be clear that if $$$N$$$ has any non-trivial divisors, they will be closer to $$$\lfloor N/2 \rfloor$$$ than the trivial divisors $$$1$$$ and $$$N$$$ are. Therefore, we could factorize any $$$N$$$ by finding this closest divisor $$$d$$$ -- if it is $$$1$$$ (or $$$N$$$) then $$$N$$$ is prime, if it is not, then we recursively factorize $$$d$$$ and $$$N/d$$$.

      EDIT: To add to this, it is an open problem whether factoring can be solved in $$$O(\log^k n)$$$ time for some $$$k$$$.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Any positive divisors right ?

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You mean like rho algorithms ?

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        If the complexity is like that... Is there a possible happen where it has the worst case of log(n) ^ k would be far bigger than sqrt(n) right ?

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you pick M = ⌊N/2⌋ is that mean the closest divisor c is N / fp where fp is the smallest prime divisor of N ?

    → Reply