Projet Euler Original Method Group 1

J'ai fait une méthode liée aux nombres premiers qui est souvent utilisée dans Project Euler. J'ai également écrit un test simple. Il vaut peut-être mieux utiliser des outils de test tels que UnitTest, mais je ne connais pas les spécifications de ces outils, donc je l'ai écrit de manière appropriée. ファイル名:mymath.py

# coding:utf-8
import math

def get_prime_boolean(max):
    bool = [False,False]+[True]*(max-1)
    #Faire des multiples de 2 faux
    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()

Recommended Posts

Projet Euler Original Method Group 1
Projet Euler 37
Projet Euler 7
Projet Euler 47
Projet Euler 31
Projet Euler 4
Projet Euler 17
Projet Euler 26
Projet Euler 8
Projet Euler 23
Projet Euler 19
Projet Euler 50
Projet Euler 42
Projet Euler 33
Projet Euler 32
Projet Euler 43
Projet Euler 35
Projet Euler 36
Projet Euler 24
Projet Euler 46
Projet Euler 48
Projet Euler 45
Projet Euler 6
Projet Euler 44
Projet Euler 39
Projet Euler 40
Projet Euler 49
Projet Euler 29
Projet Euler 27
Projet Euler 41
Projet Euler 18
Projet Euler 13
Projet Euler 30
Projet Euler 16
Projet Euler 14
Projet Euler 34
Projet Euler 25
[Projet Euler] problème1
Projet Euler15 "Chemin du treillis"
Project Euler 2 Acceleration 2.21 Économisez des microsecondes.
Qu'est-ce que Project Euler 3 Acceleration?
Programmation fonctionnelle dans Python Project Euler 1
Projet Euler 10 "Somme des nombres premiers"
[Note] Projet Euler en Python (problème 1-22)
Programmation fonctionnelle dans Python Project Euler 3
Projet Euler # 5 "Minimum Multiple" en Python
Projet Euler 4 Tentative d'accélération
Programmation fonctionnelle dans Python Project Euler 2
Projet Euler 11 "Produit maximum dans la grille"
Projet Euler # 15 "Lattice Path" en Python
Projet Euler # 4 "Calligraphie maximum" en Python
Projet Euler 9 Conservation des résultats des calculs