Python: don't sort!


#1

Um, why is everyone sorting? Just prepare the results in the right order. I did this to keep it simple:

Generate all “small” factors s such that s <= sqrt(A)
When you find a small factor s, also write down its paired “big” factor b such that s*b = A, in a separate list.

I also put in a special case for A==1 and just wrote down 1 and A as known factors otherwise. Also checked to make sure I didn’t duplicate a factor, for the perfect square case.

Like this for A=12: (Sqrt A is between 3 and 4)
small factors: 1, 2, 3
big factors: 12, 6, 4

Now combine the small factors with the reverse of big factors: 1, 2, 3 … 4, 6, 12

class Solution:
	# @param A : integer
	# @return a list of integers
	def allFactors(self, A):
        result = [1]
        others = [A]
	    if A == 1:
	        return result
        for i in range(2, int(A**0.5)+1):
            if A % i == 0:
                result.append(i)
                if i * i != A:
                    others.append(A // i)
        result.extend(others[::-1])
        return result