• + 0 comments

    Python golfing, 3 lines, O(sqrt(n))

    divs = {i for i in range(2,int(math.sqrt(n))+1) if n%i==0}
    divs|= {n//i for i in divs}|{n}
    return sum(not i&1 for i in divs)
    

    Bonus optimizations with bithacks which bring down runtime a lot but still same asymptotic worst case:

    twos, n = (n&-n).bit_length()-1, n//(n&-n)
    divs = {i for i in range(3,int(math.sqrt(n))+1,2) if n%i==0}
    divs|= {n//i for i in divs}
    return twos+twos*(n!=1)+len(divs)*twos 
    

    The idea is to first extract the number of 2 factors from N, then find the number of factors of the now-odd N and do some basic combinatorics to come up with the answer.