0

I don't now if I've worded the title correctly, that's probably not the name of what I'm looking for so I'll just describe it. I want to get the most equal integer divisors of a given even number. For example for 12 I would want 3 and 4 (or 4 and 3) and not 6 and 2 and not 12 and 1. I call them 'square' because 3 and 4 would make a more square shape than 6 and 2.

Other examples:

30 -> 5 and 6
48 -> 6 and 8
28 -> 7 and 4

I only want to find these divisors and no others.

Hasen
  • 121
  • 2
    Not sure what you expect here. Just do the search. Start with $\lfloor \sqrt n\rfloor$ and go down, one at a time. – lulu Oct 02 '22 at 13:02
  • @lulu "The search"? What are you referring to. I gave examples of my expected output. – Hasen Oct 02 '22 at 13:03
  • 2
    Check each term, one at a time. If your number is small enough to factor then of course you can search amongst the factors. If your number is too big to factor...well, your problem isn't any easier than that. – lulu Oct 02 '22 at 13:04
  • @lulu So if I have 30 I start with the square root of that? Really no idea what you're suggesting there. – Hasen Oct 02 '22 at 13:05
  • 1
    I don't understand your confusion. $\lfloor \sqrt {30}\rfloor$ is obviously $5$. That's a divisor, so you are done in one step. Of course this is an absolutely terrible method if your number has hundreds of digits, but factoring large numbers is really, really hard. – lulu Oct 02 '22 at 13:06
  • @lulu No idea what \lfoor30 is. The numbers would all be under 100. You mean a rounded down (floor) square root? – Hasen Oct 02 '22 at 13:08
  • That was (pretty obviously, I think) a typo for \lfloor. Now corrected. The floor function is standard, just the greatest integer which does not exceed the argument. – lulu Oct 02 '22 at 13:09
  • 1
    @lulu No it wasn't an obvious typo. I guessed it must a rounded down square root from the square root sign. What about for 28 though? – Hasen Oct 02 '22 at 13:10
  • Have you even tried? What is $\lfloor \sqrt {28} \rfloor$? – lulu Oct 02 '22 at 13:12
  • @lulu 5 doesn't help me though since I need 7 and 4. – Hasen Oct 02 '22 at 13:13
  • @lulu It also doesn't work with 40 and many others. It only works with some unless you have some further ideas. – Hasen Oct 02 '22 at 13:18
  • Do you want a more efficient solution than "factor $n$, list all the factors, check which are closest to $\sqrt{n}$"? Because I'm pretty sure no matter how you do this, you're not going to be able to avoid factoring, and that's going to be the most computationally intensive task. – Daniel Hast Oct 02 '22 at 13:25
  • 2
    As I said, go down one at a time. with $28$, you start with $5$. Doesn't work? Too bad. Go down one. Now try $4$. You are done! My method works for all $n$, though it is insanely inefficient if $n$ is very large. As I say, no known method works well for large $n$. – lulu Oct 02 '22 at 13:27
  • @Daniel Hast Well it's to be used as part of a computer program so it should be relatively simple. At the moment I can obviously come up with the values manually very easily and input them myself but it involves changing a lot of values so I'd rather it was automatic. Maybe the way you've suggested is the way to do it since the values will always be under 100. – Hasen Oct 02 '22 at 13:28
  • @lulu Ok so that's what you mean by 'go down one'. Yeah that would work pretty well. Especially since I'm dealing with small numbers. – Hasen Oct 02 '22 at 13:28
  • 1
    If the inputs are always under 100, then the fastest method is probably just precomputing the solution for each $n \leq 100$ and storing them in a lookup table. – Daniel Hast Oct 02 '22 at 13:33
  • @Daniel Hast Ok that's true although in my case here I wouldn't be bothered to do that. Lulu's method works well in my particular case. Thanks. – Hasen Oct 02 '22 at 13:37
  • @Hasen If you've got the factors, it's a straightforward search through them for the least $i$ such that $\lfloor \sqrt{n}\rfloor- i$ is a factor of $n$ (note that you only have to go down with $i$). If you've not got the factors of $n$, it's nontrivial to show that anything at all divides $n$. As has been noted, the hard part is the factorization, while the search for the divisors nearest the square root is, in comparison, relatively easy. The search for $i$ won't make the factorization any easier (or it would be a well-known algorithm). See MSE Q7377 for more. – Jam Oct 02 '22 at 13:43

0 Answers0