Euler项目-问题5-最小倍数

Question

眼前的问题是：

2520是最小的数，可以除以从1到10的每一个数，没有任何余数。什么是最小的正数，可以被从1到20的所有数字整除？

下面是我为解决这个问题而编写的代码：

from math import sqrt

def prime_factorization(n: int) -> dict:
    '''
    Returns a dict with the prime factorization of the integer n, where the keys of the dict are the prime numbers
    and the values are the powers in the factorization for the appropriate prime number key.
    :param n: an integer we want to compute he's prime factorization
    '''
    prime_dict = {}

    # dealing with even prime numbers - e.g. 2
    while n % 2 == 0:
        if 2 not in prime_dict:
            prime_dict[2] = 0
        prime_dict[2] += 1
        n = n // 2

    # dealing with odd numbers
    upper_bound = int(sqrt(n))
    for i in range(3,upper_bound+1):
        while n % i == 0:
            if i not in prime_dict:
                prime_dict[i] = 0
            prime_dict[i] += 1
            n = n // i

    # In case n is prime by itself
    if n > 1:
        prime_dict[n] = 1

    return prime_dict


def smallest_dividable_num(n:int) -> int:
    '''
    Returns the smallest integer whose dividable by all the numbers from 1 to n.
    :param n: an integer upper bound which we want to compute the smallest divisable num from 1 to it.
    '''
    prime_dict = {}
    for i in range(1,n+1):
        tmp_dict = prime_factorization(i)
        for k,_ in tmp_dict.items():
            if k not in prime_dict or prime_dict[k] < tmp_dict[k]:
                prime_dict[k] = tmp_dict[k]
    res = 1
    for k,v in prime_dict.items():
        res = res*(k**v)
    return res

下面是我为这段代码编写的一个小测试用例：

from ProjectEuler.problem5 import smallest_dividable_num

if __name__ == "__main__":
    # The prime factorization is {2**3,3**2,5,7} -> returns 2520
    print(smallest_dividable_num(10))
    # The prime factorization is {2**2,3,5} -> returns 60
    print(smallest_dividable_num(6))
    # The prime factorization is {2**4,3**2,5,7,11,13,17,19} -> returns 232792560
    print(smallest_dividable_num(20))

让我知道你对我的解决方案的想法。谢谢:)

Answer 1

处理prime_factorization

中dict中未包含的值

在prime_factorization中的两个位置，我们最终执行字典查找，在需要时设置默认值0。

这样做有多种其他方式：

我们可以使用一个变量来存储当前除数的系数：

    # dealing with even prime numbers - e.g. 2
    d = 2
    coef = 0
    while n % d == 0:
        coef += 1
        n = n // d
    if coef:
        prime_dict[d] = coef

    # dealing with odd numbers
    for d in range(3, int(sqrt(n))+1):
        coef = 0
        while n % d == 0:
            coef += 1
            n = n // d
        if coef:
            prime_dict[d] = coef

(请注意，如果我们不介意在字典中使用0，则不需要if coef )。

另一种选择可以是使用适当的数据结构。

import collections

def prime_factorization(n: int) -> dict:
    '''
    Returns a dict with the prime factorization of the integer n, where the keys of the dict are the prime numbers
    and the values are the powers in the factorization for the appropriate prime number key.
    :param n: an integer we want to compute he's prime factorization
    '''
    prime_dict = collections.defaultdict(int)

    # dealing with even prime numbers - e.g. 2
    d = 2
    while n % d == 0:
        prime_dict[d] += 1
        n = n // d

    # dealing with odd numbers
    for d in range(3, int(sqrt(n))+1):
        while n % d == 0:
            prime_dict[d] += 1
            n = n // d

或柜台：

import collections

def prime_factorization(n: int) -> dict:
    '''
    Returns a dict with the prime factorization of the integer n, where the keys of the dict are the prime numbers
    and the values are the powers in the factorization for the appropriate prime number key.
    :param n: an integer we want to compute he's prime factorization
    '''
    prime_dict = collections.Counter()

    # dealing with even prime numbers - e.g. 2
    d = 2
    while n % d == 0:
        prime_dict[d] += 1
        n = n // d

    # dealing with odd numbers
    for d in range(3, int(sqrt(n))+1):
        while n % d == 0:
            prime_dict[d] += 1
            n = n // d

然而，我倾向于把产生素数除数的逻辑和计算它们的逻辑完全分开。使用生成器，我们可以得到如下内容：

import collections

def yield_prime_factors(n: int):
    '''Yield prime factors.'''
    d = 2
    while n % d == 0:
        yield d
        n = n // d

    # dealing with odd numbers
    for d in range(3, int(sqrt(n))+1):
        while n % d == 0:
            yield d
            n = n // d

    # In case n is prime by itself
    if n > 1:
        yield n


def prime_factorization(n: int) -> dict:
    '''
    Returns a dict with the prime factorization of the integer n, where the keys of the dict are the prime numbers
    and the values are the powers in the factorization for the appropriate prime number key.
    :param n: an integer we want to compute he's prime factorization
    '''
    return collections.Counter(yield_prime_factors(n))

迭代smallest_dividable_num

中的键和值

您使用for k,_ in tmp_dict.items()，它从dict中转储值，使用tmp_dict[k]从dict中获取值。

你也可以写：

    tmp_dict = prime_factorization(i)
    for k, v in tmp_dict.items():
        if k not in prime_dict or prime_dict[k] < v:
            prime_dict[k] = v

这也可以写成：

    for k, v in prime_factorization(i).items():
        if k not in prime_dict or prime_dict[k] < v:
            prime_dict[k] = v

使用最大值和默认值

上面的代码片段可以通过利用Python内置程序来编写：

        prime_dict[k] = max(v, prime_dict.get(k, 0))

使用就地运算符

您可以编写如下内容：

        n //= d

或

    res *= (k**v)

以避免重复操作数的左成员。

一种不同的算法

该算法是一种计算最小公共倍数的算法，可以很容易地用最大公约数进行计算。

在实现这一功能并重写测试用例以确保基准给出相关的时间时：

from timeit import default_timer as timer
import functools

def gcd(a, b):
    """Computes gcd for 2 numbers."""
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    """Computes lcm for 2 numbers."""
    return a * b // gcd(a, b)


def lcmm(*args):
    """Computes lcm for numbers."""
    return functools.reduce(lcm, args)

def smallest_dividable_num(n:int) -> int:
    '''
    Returns the smallest integer whose dividable by all the numbers from 1 to n.
    :param n: an integer upper bound which we want to compute the smallest divisable num from 1 to it.
    '''
    return lcmm(*range(1, n + 1))


if __name__ == "__main__":
    start = timer()
    for i in range(20):
        assert smallest_dividable_num(10) == 2520
        assert smallest_dividable_num(6) == 60
        assert smallest_dividable_num(20) == 232792560
    for i in range(1, 40):
        smallest_dividable_num(i)
    end = timer()
    print(end - start)