Project Euler オリジナルメソッド群1

Project Eulerでよく使う素数関係のメソッドを作ってみた。
一応簡単なテストも書いてみた。UnitTestなどのテストツールなどを使ったほうが良いのかもしれないけど、それらのツールの仕様をよく知らないので、適当にオレオレで書いてみた。
ファイル名:mymath.py

# coding:utf-8
import math

def get_prime_boolean(max):
    bool = [False,False]+[True]*(max-1)
    # 2の倍数をFalseに
    bool[4::2] = [False] * (len(bool[4::2]))
    p = 3
    p_max = int(math.sqrt(max))+1
    while p<=p_max:
        if bool[p]:
          bool[p*2::p] = [False] * (len(bool[p**2::p]))
        p+=2
    return bool

def get_prime_list(bool):
    length = len(bool)
    return [i for i in range(2,length) if bool[i]]

def get_primes(max):
    bool = get_prime_boolean(max)
    list = get_prime_list(bool)
    return {'bool':bool,'list':list}

def factor(num,pri):
    ret=[]
    max = int(math.sqrt(num))
    if num < len(pri['bool']) and pri['bool'][num]:
        return [num]
    for p in pri['list']:
        while not num % p:
            ret.append(p)
            num //= p
    if num>=2:
        ret.append(num)
    ret.sort()
    return ret

def factor_dict(num,pri):
    fct_list = factor(num,pri)
    fct_dict = {}
    for i in set(fct_list):
        fct_dict[i] = fct_list.count(i)
    return fct_dict

def sum_factors(num,pri):
    if num == 0:
      return 0
    fct_dict = factor_dict(num,pri)
    ans = 1
    for k,v in fct_dict.items():
        ans *= (k ** (v+1) - 1) / (k-1)
    return ans

def get_number_of_factor(num,pri):
    d = factor_dict(num,pri)
    ans = 1
    for v in d.values():
        ans *= v+1
    return ans

def lcm_dict(num1,num2):
    ret = {}
    ret.update(num1)
    for k in num2.keys():
        if k in num1 and num1[k] < num2[k]:
            ret[k] = num2[k]
        elif not k in num1:
            ret[k] = num2[k]
    return ret

def factor_seq(max):
  ret = [[0]]
  for i in range(max):
    ret += [[1]]
  seq = range(max+1)
  for i in seq[2:max//2+1]:
    for j in seq[i*2::i]:
      ret[j] += [i]
  return ret

def factor_sum_seq(max):
  ret = [0]  + [1] * max
  seq = range(max+1)
  for i in seq[2:max//2+1]:
    for j in seq[i*2::i]:
      ret[j] += i
  return ret

def factor_num_seq(max):
  ret = [0]  + [1] * max
  seq = range(max+1)
  for i in seq[2:max//2+1]:
    for j in seq[i*2::i]:
      ret[j] += 1
  return ret

def dict2num(dict):
  r = 1
  for k in dict.keys():
    r *= k**dict[k]
  return r


def sum_nums(s,l,diff):
    n = (l - s + diff)//diff
    return (n*(s+l))/2

def sum_squars(max):
    return (max*(max+1)*(2*max+1))/6

def chk(output,expected,err_msg):
    if output == expected:
        return True
    else:
        print "output: %s" % output
        print "expected: %s" % expected 
        print err_msg
        return False

def test_get_prime_boolean1():
    input = 24
    output = get_prime_boolean(input)
    expected = [
        False, #0
        False, True, True, False, True, False, True, False, False, False, #1 to 10
        True, False, True, False, False, False, True, False, True, False, #11 to 20
        False, False, True, False #21 to 24
    ]
    return chk(output, expected, "test_get_prime_boolean1() error")

def test_get_prime_boolean2():
    input = 25
    output = get_prime_boolean(input)
    expected = [
        False, #0
        False, True, True, False, True, False, True, False, False, False, #1 to 10
        True, False, True, False, False, False, True, False, True, False, #11 to 20
        False, False, True, False, False #21 to 25
    ]
    return chk(output, expected, "test_get_prime_boolean2() error")

def test_get_prime_list1():
    input = [
        False, #0
        False, True, True, False, True, False, True, False, False, False, #1 to 10
        True, False, True, False, False, False, True, False, True, False, #11 to 20
        False, False, True, False, False #21 to 25
    ]
    output = get_prime_list(input)
    expected = [2, 3, 5, 7, 11, 13, 17, 19, 23]
    return chk(output, expected, "test_get_prime_list1() error")

def test_get_prime_list2():
    # last number is prime
    input = [
        False, #0
        False, True, True, False, True, False, True, False, False, False, #1 to 10
        True, False, True, False, False, False, True, False, True, False, #11 to 20
        False, False, True #21 to 23
    ]
    output = get_prime_list(input)
    expected = [2, 3, 5, 7, 11, 13, 17, 19, 23]
    return chk(output, expected, "test_get_prime_list2() error")

def test_get_prime_list3():
    # last number is not prime
    input = [
        False, #0
        False, True, True, False, True, False, True, False, False, False, #1 to 10
        True, False, True, False, False, False, True, False, True, False, #11 to 20
        False, False #21 to 22
    ]
    output = get_prime_list(input)
    expected = [2, 3, 5, 7, 11, 13, 17, 19]
    return chk(output, expected, "test_get_prime_list3() error")

def test_get_primes():
    input = 25
    output = get_primes(input)
    expected = {'bool':[
        False, #0
        False, True, True, False, True, False, True, False, False, False, #1 to 10
        True, False, True, False, False, False, True, False, True, False, #11 to 20
        False, False, True, False, False #21 to 25
    ],
    'list':[2, 3, 5, 7, 11, 13, 17, 19, 23]}
    return chk(output, expected, "test_get_primes() error")

def test_factor1():
    input1 = 23
    input2 = {'bool':[
        False, #0
        False, True, True, False, True, False, True, False, False, False, #1 to 10
        True, False, True, False, False, False, True, False, True, False, #11 to 20
        False, False, True, False, False #21 to 25
    ],
    'list':[2, 3, 5, 7, 11, 13, 17, 19, 23]}
    output = factor(input1,input2)
    expected = [23]
    return chk(output, expected, "test_factor1() error")

def test_factor2():
    input1 = 625
    input2 = {'bool':[
        False, #0
        False, True, True, False, True, False, True, False, False, False, #1 to 10
        True, False, True, False, False, False, True, False, True, False, #11 to 20
        False, False, True, False, False #21 to 25
    ],
    'list':[2, 3, 5, 7, 11, 13, 17, 19, 23]}
    output = factor(input1,input2)
    expected = [5,5,5,5]
    return chk(output, expected, "test_factor2() error")

def test_factor3():
    input1 = 619
    input2 = {'bool':[
        False, #0
        False, True, True, False, True, False, True, False, False, False, #1 to 10
        True, False, True, False, False, False, True, False, True, False, #11 to 20
        False, False, True, False, False #21 to 25
    ],
    'list':[2, 3, 5, 7, 11, 13, 17, 19, 23]}
    output = factor(input1,input2)
    expected = [619]
    return chk(output, expected, "test_factor3() error")

def test_factor4():
    input1 = 100
    input2 = {'bool':[
        False, #0
        False, True, True, False, True, False, True, False, False, False, #1 to 10
        True, False, True, False, False, False, True, False, True, False, #11 to 20
        False, False, True, False, False #21 to 25
    ],
    'list':[2, 3, 5, 7, 11, 13, 17, 19, 23]}
    output = factor(input1,input2)
    expected = [2,2,5,5]
    return chk(output, expected, "test_factor4() error")

def test_factor_dict1():
    input1 = 100
    input2 = {'bool':[
        False, #0
        False, True, True, False, True, False, True, False, False, False, #1 to 10
        True, False, True, False, False, False, True, False, True, False, #11 to 20
        False, False, True, False, False #21 to 25
    ],
    'list':[2, 3, 5, 7, 11, 13, 17, 19, 23]}
    output = factor_dict(input1,input2)
    expected = {2:2,5:2}
    return chk(output, expected, "test_factor_dict1() error")

def test_factor_dict2():
    input1 = 97
    input2 = {'bool':[
        False, #0
        False, True, True, False, True, False, True, False, False, False, #1 to 10
        True, False, True, False, False, False, True, False, True, False, #11 to 20
        False, False, True, False, False #21 to 25
    ],
    'list':[2, 3, 5, 7, 11, 13, 17, 19, 23]}
    output = factor_dict(input1,input2)
    expected = {97:1}
    return chk(output, expected, "test_factor_dict2() error")

def test_lcm_dict():
    input1 = {2:2,3:3}
    input2 = {2:4,5:1}
    output = lcm_dict(input1,input2)
    expected = {2:4,3:3,5:1}
    return chk(output, expected, "test_lcm_dict() error")

def test_time(func,input,name,ok_time):
    import time
    start = time.time()
    func(input)
    end = time.time()
    if end-start <= ok_time:
        print "%s finished in time." % name
        print end-start
        return True
    else:
        print "!!!WARING!!! %s dose not finished in time." % name
        print end-start
        return False

def test_time_get_prime_boolean():
    return test_time(get_prime_boolean,10**6,"get_prime_boolean",0.2)

def tests():
    test_list = [ 
        test_get_prime_boolean1,
        test_get_prime_boolean2,
        test_get_prime_list1,
        test_get_prime_list2,
        test_get_prime_list3,
        test_get_primes,
        test_factor1,
        test_factor2,
        test_factor3,
        test_factor4,
        test_factor_dict1,
        test_factor_dict2,
        test_lcm_dict,
        test_time_get_prime_boolean
    ]
    fail = 0
    for test in test_list:
        if not test():
            print test
            fail += 1
    if fail == 0:
        print "All test was successful!"
    else:
        print "%d tests failed!" % fail


if __name__=='__main__': 
    tests()