For the math nerds...

[ofnuts]

@Warren Hill: looking at your post it dawns on me that if there are N factors there are 2^N divisors to test (with likely many duplicates, but I don't care) and the binary form of the value iterated from 0 to 2^N-1makes it easy to compute the divisor... And if you take this value as path in a binary tree, and set the node value to the corresponding divisor, you can cut off everything beyond the nodes where the divisor is greater than the square root.

@trent.josephsen: yes, alas

@Bachstelze: everything is easier with the right library but yes, iterating the divisors is likely the best solution (see above)

@Vaphell: nice awk hack!

@spjackson: yes, this limits the number of divisors to check (or to compute)

[Warren Hill]

Sorry you are correct I am missing a few 5s

If we take total pixels P = 480000 for example

Then in C

int x,y;

for (x = sqrt(P); x > 0; x--){
        y = P / x;
       if (x * y == P){
        printf( "Possible solutions %d x %d, and %d x %d \n", x, y, y,x);
    }
}

Is probably the simplest and while it may not be the fastest. It should be fast enough for images where the total number of pixels is less than a few million on most computers

[Vaphell]

y = P / x;
if (x * y == P)...

dont we have % for that?
otherwise i agree it's not worth the effort to think much about this problem, unless for mental gymnastics. Complexity of sqrt(n) nets you 10^6 operations for 10^12 magnitude input and that is what, less than a second of cpu time?

[Warren Hill]

True

Instead of

if ( x * y == P)

if (x % y ==0)

or

if (!(x % y))

also works and may be slightly quicker, if less easy to understand

[iMac71]

from math import sqrt
def find_wh(n):
    sqrt_n = int(sqrt(n))
    for w in range(sqrt_n, 0, -1):
        h, remainder = divmod(n, w)
        ratio = float(h) / w
        if remainder == 0 and ratio >= 1 and ratio <= 2:
           print h, w 

[hardmath]

Searching for two factors close to the square root of N is the strength of Fermat's factoring method.

Where trial division starts small and goes up (at least typically), Fermat's method starts with the first square a^2 greater than or equal to N and checks if a^2 - N happens to be another square b^2. If so, then N = a^2 - b^2 = (a+b)(a-b) and we have our most nearly equal factors of N.

If that fails, increment a, etc. and test again, until a factorization is found or a reaches (N-1)/2, after which point if N is odd we find:

[(N+1)/2]^2 - N = [(N-1)/2]^2

implying the trivial factorization N = N*1.

In practice here we would stop once (a+b)/(a-b) exceeds the allowable aspect ratio, e.g. 2.

[ofnuts]

Thanks for the tip...