Pages

2012-09-05

Divisors.

I've been thinking about how to find divisors of an integer i (supposedly between 10 and 100 or so) manually and as effortlessly as possible.
I wrote the code below to check if the results are correct by comparison with a simple brute-force way.
In hand calculation, you have to find an integer a that satisfies the condition a 2 i < a + 1 2 instead of math.sqrt(i).

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# divisors.py - returns list of divisors
import math, sys, traceback

def check1by1(int_num): # check all numbers from 1 to int_num.
    int_num = abs(int_num)
    if int_num == 0:
        return None
    else:
        div_list = []
        for i in range(1, int_num + 1):
            if int_num % i == 0:
                div_list.append(i)
        return div_list

def getdivisors(int_num): # avoid unnecessary calculation.
    """Return list of divisors of int_num. (None if int_num == 0.)"""
    int_num = abs(int_num)
    if int_num == 1:
        return [1]
    elif int_num == 0:
        return None
    else:
        div_list = [1, int_num]
        start = 2
        step = 1
        if int_num % 2 != 0: # if int_num is odd, even divisors are excluded.
            start = 3
            step = 2
        for i in range(start, int(math.sqrt(int_num)) + 1, step):
            if int_num % i == 0:
                div_list.append(i)
                if i != int_num / i:
                    div_list.append(int_num / i)
        return sorted(div_list)

if __name__ == '__main__':
    try:
        num = int(sys.argv[1])
    except IndexError:
        print('usage: python divisors.py integer')
        sys.exit(0)
    simple = check1by1(num)
    print('check1by1  ', num, simple)
    shortcut = getdivisors(num)
    print('getdivisors', num, shortcut)
    if simple != shortcut: # Error checking.
        print('Error.')

Update, September 7, 11:43 p.m. JST: xrange() instead of range(), benchmark().
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# divisors.py - returns list of divisors
import math, sys, time

def benchmark(int_num, fn):
    start_time = time.clock()
    result = fn(int_num)
    elapsed_time = time.clock() - start_time
    return result, elapsed_time

def check1by1(int_num): # check all numbers from 1 to int_num.
    int_num = abs(int_num)
    if int_num == 0:
        return None
    else:
        div_list = []
        for i in xrange(1, int_num + 1):
            if int_num % i == 0:
                div_list.append(i)
        return div_list

def getdivisors(int_num): # avoid unnecessary calculation.
    """Return list of divisors of int_num. (None if int_num == 0.)"""
    int_num = abs(int_num)
    if int_num == 1:
        return [1]
    elif int_num == 0:
        return None
    else:
        div_list = [1, int_num]
        start = 2
        step = 1
        if int_num % 2 != 0: # if int_num is odd, even divisors are excluded.
            start = 3
            step = 2
        for i in xrange(start, int(math.sqrt(int_num)) + 1, step):
            if int_num % i == 0:
                div_list.append(i)
                div_result = int_num / i
                if i != div_result:
                    div_list.append(div_result)
        return sorted(div_list)

if __name__ == '__main__':
    try:
        num = int(sys.argv[1])
    except IndexError:
        print('usage: python divisors.py integer')
        sys.exit(0)
    simple = benchmark(num, check1by1)
    shortcut = benchmark(num, getdivisors)
    if simple[0] != shortcut[0]: # Error checking.
        print('Error.')
    print('check1by1  ', num, simple)
    print('getdivisors', num, shortcut)
    print('time difference: ' + str(simple[1] - shortcut[1]) + ' sec.')

No comments: