Time limit exceeded on finding out the GCD and LCM of a Python list

I'm doing this HackerRank problem:


Consider two sets of positive integers, \$A=\{a_0, a_1, \ldots, a_{n-1}\}\$ and \$B=\{b_0, b_1, \ldots, b_{m-1}\}\$. We say that a positive integer, \$x\$, is between sets \$A\$ and \$B\$ if the following conditions are satisfied:

• All elements in \$A\$ are factors of \$x\$.

• \$x\$ is a factor of all elements in \$B\$.

Given \$A\$ and \$B\$, find and print the number of integers (i.e., possible \$x\$'s) that are between the two sets.

Assuming lists a and b as in the problem, the main idea is finding the LCM of list a and the GCD of list b, and then finding out how many multiples of the LCM divide the GCD perfectly without remainders. I ended up with this -

from fractions import gcd

def lcm(a, b):
    for i in xrange(max(a,b), a*b+1):
        if i%a==0 and i%b==0:
            l = i
            break
    return l

def count(l, g):
    count = 1
    if l==g:
        return count
    elif g%l !=0 and l%g != 0:
        return 0
    elif l<g:
        for i in xrange(l, g, l):
            if g%i==0:
                count += 1
        return count
    else:
        for i in xrange(g, l, g):
            if l%i==0:
                count +=1 
        return count

if __name__ == '__main__':
    n,m = raw_input().strip().split(' ')
    n,m = [int(n),int(m)]
    a = map(int,raw_input().strip().split(' '))
    b = map(int,raw_input().strip().split(' '))
    l = reduce(lcm, a)
    g = reduce(gcd, b)
    print count(l, g)

But I pass only 7 of the 8 test cases, the last one getting terminated due to time out. I don't understand which part of my code would result in a long loop that might end up in a timeout.

P.S. I would also be very glad if any of you could point out any other inefficiencies or styling conventions in my code.

• It is a really bad idea to use a variable named l. I is hard to distinguish it from 1.

• All these functions using xrange are inefficient

the lcd function can be efficiently calculated by

from fractions import gcd
def lcd(a,b):
    return(a*b/gcd(a,b))

the count function is

count(l,g)=divisor_count(g/l)

where divisor_count is the number-of-divisors function

If the number n has the prime factor decomposition

$$n=p_1^{e_1}\cdot p_2^{e_2}\cdots p_k^{e_k}$$
then we have

$$ \text{divisor_count}(n)=(e_1+1)\cdot(e_2+1)\cdots(e_k+1)$$

This can be calculated in the following way:

def divisor_count(n):
    cnt=1
    i=2
    while i*i1:
        cnt*=2
    return(cnt)

This divisor_count function runs in
$$O(\sqrt{n})$$
time, the xrange implementation uses
$$O(n)$$
time.

StackExchange Code Review Q#149798, answer score: 4