Algorithm to minimize surface area, given volume
Here is a modified version of a "choose divisor near cube root" algorithm.  It still must brute force many cases, so I'm not sure how much of a real improvement it is speed wise over the enumeration of all cases.  However, I submitted it as a correction to the algorithm on OEIS (that which generated incorrect results) because I believe it should be accurate at least. 

Here is the algorithm to find (s1,s2,s3) and surface area of a rectangular prism given its volume n:


Given n, find the cube root.    
Set an initial value integer s1 at the ceiling of that cube root.    
Test to see if s1 is a divisor of n, and if not, reduce s1 by 1.    
If a divisor s1 is found, set an initial s2 to be the ceiling of the square root of (n/s1).    
Then test to see if s2 is a divisor of n/s1, and if not, reduce s2 by 1.    
When a divisor s2 is found, s3 then is set to n/(s1*s2).
The current surface area is calculated by 2*(s1*s2 + s1*s3 + s2*s3).
The current SA is compared against the current minimum.  If its the first surface area calculated, it is stored as minSA. After the first, we test to see if the current SA is smaller than minSA, and if so, store it in minSA.


This algorithm enumerates some of the triples (s1,s2,s3) but needs only to test the divisors under the cube root. (Since not all three divisors can be above the cube root).  In a similar fashion, s2 needs only to test divisors of n/s1 under the square root of n/s1, since not both divisors can be above the square root) 

A note on step 3: if the cube root is a divisor then n is a cube and we can stop there with minimal surface area 6*s1^2 from the box (s1,s1,s1).

Python:

import math
def minSArectprism(n):
    s1_0 = int(math.ceil(n ** (1 / 3.0))) 
    minSA=-1
    s1 = s1_0
    while s1&gt;=1:
        while n % s1 &gt; 0:  
            s1 = s1 - 1
        s1quot = int(n/s1) 
        s2_0 = int(math.ceil(math.sqrt(n/s1)))
        s2 = s2_0
        while s2&gt;=1:
            while s1quot % s2 &gt; 0:
                s2 = s2 - 1
            s3 = int(n / (s1 * s2))  
            SA = 2*(s1*s2 + s1*s3 + s2*s3)  
            if minSA==-1:
                minSA=SA
            else:
                if SA&lt;minSA:
                    minSA=SA
            s2 = s2 - 1
        s1 = s1 - 1    
    return minSA