Packaging Cupcakes problem - Help

Hi,

While solving the problem packaging cupcakes I was able to come up with a solution but got time limit exceeded error upon submission.

my logic: store all the remainders in a list, get the indices of the max remainder and output index + 1

upon seeing the submitted solutions I noticed that people have used the formula n/2 + 1 where n is the number of cupcakes.

my code:
import random
def get_rem(n):
    remainder = []
    for i in range(1, n+1):
        rem = n % i
        remainder.append(rem)
    # print "rem: ", remainder
    # remainder = [4, 7, 9, 4, 1, 6, 9]
    max_value = max(remainder)
    if remainder.count(max_value):
        max_l = [i for i, j in enumerate(remainder) if j == max_value]
        print "max remainder pos:", max_l
        max_div = int(max(max_l)) + 1
        # print "Type:", type(max_div)
        print max_div


# t = int(raw_input())
# for i in range(t):
#     n = int(raw_input())
#     get_rem(n)

# for testing
t = random.randint(1, 1000)
print t
for i in range(t):
    n = random.randint(2, 10 ** 8)
    print n
    get_rem(n)

can any one please tell me how can i fix the time limit exceeded error and why am i getting it also can please explain the n/2 + 1 logic