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
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 ).
Thanks <3
But if there is just one query, can I approach faster than
O(√(n))
?Why I cant see your ideone code ?
Weird. It should be visible.
Can you show me the source code or pseudo code ?
oh, ok thanks <3
We can use this as sieve right ?
Yes.
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.
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)?
Right, 'reduces to factoring' would be a better way to phrase it.
Sorry but I dont understand what is
non-trivial divisor
meaning. Is that mean I cant use theO(√(n))
approach ?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$$$.
Any positive divisors right ?
You mean like rho algorithms ?
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 thansqrt(n)
right ?If you pick
M = ⌊N/2⌋
is that mean the closest divisorc
isN / fp
wherefp
is the smallest prime divisor of N ?