

In [ ]:

    
%autosave 0

Divisor

Number of Divisor

Write a function which returns the number of divisor (including 1 and itself).

Example:

Input: 5, Output: 2 (1, 5)
Input: 12, Output: 6 (1, 2, 3, 4, 6, 12)
Input: 49, Output: 3 (1, 7, 49)



In [ ]:

    
# Simple but not efficient answer

def num_div0(n):
    '''
    n: Integer (bigger than 0)
    output: Number of Divisor (Including 1 and n)
    '''
    
    count_div = 0
    for div in range(1, n+1):   # 1 - n
        if n % div == 0:
            count_div += 1
            
    return count_div



In [ ]:

    
print (5, num_div0(5))
print (12, num_div0(12))
print (49, num_div0(49))



In [ ]:

    
# This function is not efficient, so it's difficult to handle big input
print (9999999, num_div0(9999999))

Java version of simple algorithm

class num_div {

    static int num_div0(int n) {
        int count_div = 0 ;
        for (int div=1; div<=n; div++) {
            if (n % div == 0) count_div++ ;
        }
        return count_div ;
    }

    public static void main(String argv[]) {

        System.out.printf("%d %d\n", 5, num_div0(5)) ;
        System.out.printf("%d %d\n", 12, num_div0(12)) ;
        System.out.printf("%d %d\n", 49, num_div0(49)) ;
    }
}

How to improve the performance

Hint: Prime number checking



In [ ]:

    
# Faster than version 0

def num_div1(n):
    '''
    n: Integer (bigger than 0)
    output: Number of Divisor (Including 1 and n)
    '''
    
    import sys
    count_div = 0
    sqrt_n = (int)(n**0.5)
    for div in range(1, sqrt_n+1):   # 1 - n
        if n % div == 0:
            count_div += 1
            qt = n // div
            print('(', n, '/', div, '=', qt, ')', end = ' ', file=sys.stderr)
            if n // div != div:  # quatient != div
                count_div += 1
            
    print('Number of divisor:', count_div, file=sys.stderr)
    return count_div



In [ ]:

    
print (5, num_div1(5))
print (12, num_div1(12))
print (49, num_div1(49))
print (9999999, num_div1(9999999))

Java version

class num_div {

    static int num_div0(int n) {
        int count_div = 0 ;
        int sqrt_n = (int)Math.sqrt((double)n) ;
        for (int div=1; div<=sqrt_n; div++) {
            if (n % div == 0) {
                count_div++ ;
                int qt = n / div ;
                if (qt != div) count_div++ ;
            }
        }
        return count_div ;
    }

    public static void main(String argv[]) {

        System.out.printf("%d %d\n", 5, num_div0(5)) ;
        System.out.printf("%d %d\n", 12, num_div0(12)) ;
        System.out.printf("%d %d\n", 49, num_div0(49)) ;
    }
}

Further improvement

Every interger can be represented as prime factorized format. $2^{c0}\cdot 3^{c1}\cdot 5^{c2} \cdot 7^{c3} ... (cx >= 0)$ In that case, number of divisor is calculated as $(c0+1) \cdot (c1+1) \cdot (c2+1) \cdot (c3+1) ...$ Because every divisors are combination of the prime factor of input number.

Example $12=2^2\cdot3^1$, Num of Divisor $(2+1)\cdot(1+1)=6$

Divisor: $2^0\cdot 3^0=1\\2^1\cdot 3^0=2\\2^2\cdot 3^0=4\\2^0\cdot 3^1=3\\2^1\cdot 3^1=6\\2^2\cdot 3^1=12$

Question

What is the smallest integer that has 100 divisors (including 1 and itself) ?



In [ ]:

    
# 2**99 (99+1=100) = 633825300114114700748351602688
# 2**9 * 3**9 ((9+1)*(9+1)=100) = 10077696
# 2**9 * 3**4 * 5 (10*5*2=100) = 207360
# 2**4 * 3**4 * 5**3 (5*5*4=100) = 162000
# 2**4 * 3**4 * 5 * 7 (5*5*2*2=100) = 45360
print(num_div1(45360))



In [ ]: