Getting factors of a number with least sum in O(1)

Question

I'm trying to find the factor pair of a number with least sum in O(1).

Here is the explanation :

If number is 100. Then all the possible pairs are :

1    X  100
2    X  50
4    X  25
5    X  20
10   X  10
20   X  5
25   X  4
50   X  2
100  X  1

Here the pair with least sum is 10,10 which is clearly the middle one

Similarly if number is 12 then pairs are as follows

1  X  12
2  X  6
3  X  4
4  X  3
6  X  2
12 X  1

Here the required pair is either 3,4 or 4,3.

If a number has 'p' pairs then the required one is always ceil(p/2).

If the given number is a perfect square then the task is pretty simple.The pair would be just sqrt(number),sqrt(number).

If not then the pair would be either ceil(sqrt(number)),number/ceil(sqrt(number))

given that ceil(sqrt(number)) is a factor of number

or the immediate factor neighbour of sqrt(number):

For example consider '6'. 6 is not a perfect square.

ceil of sqrt(6) is 3 and 3 is a factor of 6.So the required pair is 3,6/3=2

Now consider 102. All pairs are :

1  *  102.0
2  *  51.0
3  *  34.0
6  *  17.0
17  *  6.0
34  *  3.0
51  *  2.0
102 *  1

The required pair in this is 17,6 or 6,17. Here ceil(sqrt(102)) is 11. The immediate factor neighbour of 11 is 17 or 6. Now this is what we actually find.

How do we find that immediate factor neighbour ?

Here is my O(n) implementation :

import math

l = []
n = int(input())
for i in range(1, n + 1):
    if n % i is 0:
        l.append(i)
middle = l[math.ceil(len(l) / 2)]
print("Required pair is ", middle, ",", n / middle)

Answer 1

Here is the proof that finding the pair must at least be as hard as integer factoring (which implies there is no known O(1) algorithm):

If we start with a number N and get the pair with the smallest sum, as it was shown, the divisors are the closest to the sqrt(N) so there only 2 possibilities:
1. The pair is 1 - N which means N is a prime. Which is the trivial case.
2. We found some non-trivial divisor k. Which means we can apply the algorithm successively for k and N/k, eventually finding all the prime divisors efficiently.