经济及社会理事会2015年竞赛:问题1

Question

这是我的解决方案，经济合作组织2015竞赛，问题1，分形。我希望有任何建议，以提高可读性，风格，组织等。

def main():
    number = int(input())
    fractorial = {}
    for i in range(2, number + 1):
        prime_factorization = prime_factor(i)
        update_fractorial(prime_factorization, fractorial)

    print(compute_fractorial_value(fractorial))


def prime_factor(number):
    primes = [2, 3, 5, 7, 11, 13, 17, 19]
    dict = {}
    i = 0
    while i < len(primes):
        p = 0
        while number % primes[i] == 0:
            number = number // primes[i]
            p += 1

        if p != 0:
            dict[primes[i]] = p

        i += 1

    return dict


def update_fractorial(prime_factorization, fractorial):
    for key in prime_factorization:
        if key in fractorial:
            if prime_factorization[key] > fractorial[key]:
                fractorial[key] = prime_factorization[key]
        else:
            fractorial[key] = prime_factorization[key]

        # Or should I replace the if/else statements with:
        #
        # if key in fractorial:
        #   if prime_factorization[key] < fractorial[key]:
        #      break
        #
        # fractorial[key] = prime_factorization[key]
        #
        # since it is shorter.


def compute_fractorial_value(fractorial):
    value = 1
    for key in fractorial:
        value *= key ** fractorial[key]

    return value


main()

Answer 1

您的迭代技术对于Python来说有点笨拙：

• 在prime_factor()中，while i < len(primes):循环最好写成for prime in primes:。
• 在compute_factorial_value()中，for key in factorial:循环最好写成for prime, exponent in factorial.items():。
• 总的来说，使用collections.Counter而不是dict来存储素因式分解会稍微好一些。好处是Counter中的每个值都是隐式的0，所以您不必担心不存在的键。

还可以提高清晰度：

• 令人费解的是，在一个以计算一个数字的分形为目标的练习中，没有fractorial(n)函数。
• 按照惯例，在定义依赖于这些函数的函数之前，组织代码将更原始的助手函数放在第一位。因此，main()应该出现在最后。
• update_fractorial()和compute_fractorial_value()函数实际上并不是专门用于分形的，因此应该更笼统地命名。

建议重写

from collections import Counter

def prime_factors(number):
    assert number <= 22
    factors = Counter()
    for prime in [2, 3, 5, 7, 11, 13, 17, 19]:
        while number % prime == 0:
            number //= prime
            factors[prime] += 1
    return factors

def update_factors(factors, new_factors):
    for factor in new_factors:
        factors[factor] = max(factors[factor], new_factors[factor])

def multiply_factors(factors):
    value = 1
    for prime, exponent in factors.items():
        value *= prime ** exponent
    return value

def fractorial(n):
    factors = Counter()
    for i in range(2, n + 1):
        update_factors(factors, prime_factors(i))
    return multiply_factors(factors)

if __name__ == '__main__':
    print(fractorial(int(input())))

简单解

正如@hjpotter92 92所指出的，分形只不过是所有数到n的LCM，答案可以用更少的代码来计算。请注意，functools.reduce()是一种特殊类型循环的更优雅的缩写。(如果您考虑使用内置的math.gcd()进行欺骗，可以使用使用欧几里德算法很容易地重新实现。。)

请注意，挑战说您应该准备好接受一个包含多行的输入文件，这是您不支持的。我用过fileinput.input()来帮助它。

import fileinput
from functools import reduce
from math import gcd

def fractorial(n):
    lcm = lambda a, b: a * b // gcd(a, b)
    return reduce(lcm, range(1, n + 1))

def main():
    for line in fileinput.input():
        n = int(line)
        print('Fractorial ({0}) = {1}'.format(n, fractorial(n)))

if __name__ == '__main__':
    main()