Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Qual é o menor número positivo que é divisível por todos os números de 1 a 20?

+3 votos
758 visitas
perguntada Nov 10, 2016 em Programação Computacional por Edmar Rocha Pereira (21 pontos)  

2520 é o menor número que pode ser dividido por cada um dos números de 1 a 10 com resto zero. Qual é o menor número positivo que é divisível por todos os números de 1 a 20?

Gerar um código em Python que consiste em testar qual é o menor número positivo que é divisível por todos os números de 1 a 20.

Compartilhe
comentou Nov 10, 2016 por Edmar Rocha Pereira (21 pontos)  
editado Dez 9, 2016 por Edmar Rocha Pereira

Na solução temos o código em Python e depois código comentado .

2 Respostas

+1 voto
respondida Dez 7, 2016 por Edmar Rocha Pereira (21 pontos)  
editado Dez 12, 2016 por Edmar Rocha Pereira

# Código Python indentado:

    from functools import reduce

    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a

    def lcm(a, b):
        return a * b // gcd(a, b)

    def lcmm(args):
        return reduce(lcm, args)

    print(lcmm(range(1, 20)))

\[\]

# Código em Python comentado:
\[\]
\(1.º\) bloco do código:

from functools import reduce

O módulo functools é para funções de ordem superior: funções que atuam sobre ou retornam outras funções.

Em geral, qualquer objeto chamado pode ser tratado como uma função para os propósitos deste módulo. No caso específico deste código, está chamando a função reduce ().

reduce() é uma função do Python que passou a estar disponível no módulo functools a partir da versão 3000.

Sua utilidade está na aplicação de uma função a todos os valores do conjunto, de forma a agregá-los todos em um único valor.

Por exemplo, para aplicar a operação de soma a todos os elementos de uma sequência, de forma que o resultado final seja a soma de todos esses elementos, poderíamos fazer o seguinte:

import operator #necessário para obter a função de soma
valores = [1, 2, 3, 4, 5]
soma = reduce(operator.add, valores)
print soma

\[\]
\(2.º\) bloco do código:

def gcd(a, b):
while b: 
a, b = b, a % b
return a

A função gcd() retorna o maior divisor comum dos inteiros a e b.

Se a ou b é diferente de zero, então o valor absoluto de gcd (a, b) é o maior inteiro que divide tanto a como b.

A função gcd (a, b) tem o mesmo sinal de b se b é diferente de zero; Caso contrário, leva o sinal de a. A função (0, 0) retorna 0.

Outro ponto importante deste bloco é a estrutura de repetição "while", que é um comando que manda um bloco de código ser executado enquanto uma condição não for satisfeita.

O while é um comando muito útil, mas pode ser perigoso, pois se não tratarmos corretamente o critério de parada, o laço pode não ter fim, e o programa não faz o que deveria.

Abaixo segue exemplo de código que usa o "while", onde é mostrada a mensagem x > 0 até que x seja igual a zero. Quando o valor de x passar para 0, a verificação x>0 retornará falso, o programa sai do laço.

i = 0
while True:
    print "Não vou parar nunca!"
    i = i + 1
    if i > 100:
        break

\[\]

\(3.º\) bloco do código:

def lcm(a, b):
return a * b // gcd(a, b)   

Já a função lcm (a,b) vai retornar o menor múltiplo comum entre a e b.

\[\]
\(4.º\) bloco do código:

def lcmm(*args): 
return reduce(lcm, args)

lcmm(*range(1, 20))

Retorna lcm de args.

Args é usado principalmente em definições de função, que permitem que você passe um número variável de argumentos para uma função.

Na função def lcmm (* args): o * captura os argumentos posicionais em args. Isso significa que args obtém o valor (1, 2, 3, ...,19). Isso explica que estamos recebendo o mesmo que reduce (lcm, range (1,20)).

Em lcmm (* range (1,20)) está descompactando o intervalo iterável (1, 20) com *, então, está chamando lcmm (1, 2, 3, ..., 19). Em outras palavras, existem 20 argumentos que não têm nomes, mas estão em ordem e são passados nessas posições.

\[\]
\(5.º\) bloco do código:

print(lcmm(range(1, 20)))

Imprime o menor número desejado

No caso de divisores de 1 a 20, o menor número positivo divisível por todos eles será:

232.792.560.

comentou Dez 7, 2016 por danielcajueiro (5,376 pontos)  
Se vc não usar o editor de código, fica impossível entender o código e a indentação.
comentou Dez 7, 2016 por Caue (231 pontos)  
O // funcionou como comentário no seu código? Em python deve usar o # para comentário de linha.
Além disso, não entendi o lcmm(100, 23, 98) e sua relação com o problema.
comentou Dez 7, 2016 por Edmar Rocha Pereira (21 pontos)  
Opa professor! estava fazendo prova de econometria hoje! tinha postado só um rascunho da resposta! Amanha estará tudo Ok! Abraços.
comentou Dez 8, 2016 por Caue (231 pontos)  
Seria legal utilizar o recurso para apresentar código fonte do PRorum e respeitar a indentação do código, que faz diferença para o Python.
Acho que faltou explicar como funciona o algoritmo e o uso da função reduce.
+1 voto
respondida Dez 8, 2016 por Caue (231 pontos)  

Uma outra solução interessante para o problema utiliza o seguinte raciocínio:

Montamos uma lista com os número de 1 a 20. Se multiplicarmos todos os números da lista, teremos um número que é divisível por todos os números de 1 a 20.

Porém, esse número não é o menor, pois vários números na lista possuem fatores em comum, ou seja, estamos multiplicando várias vezes o mesmo fator. Exemplo: Se já multiplicamos o 2 e o 3, não precisamos mais multiplicar por 6, pois 6 = 2 x 3.

Portanto, sempre após multiplicar o resultado pelo próximo número, devemos dividir todos os número restantes da lista por aquele número, caso seja um múltiplo. Caso não seja múltiplo, não precisa fazer a divisão, pois não haverá aquele fator para eliminar.

O algoritmo ignora o número 1 na lista sempre que aparece, por ser elemento neutro da multiplicação.

A implementação está detalhada abaixo:

def calculate_least_common_multiple(n=20):
    integers = list(range(2, n + 1))
    lcm = 1
    while len(integers) > 0:
        first = integers.pop(0)
        if first == 1:
            continue
        lcm *= first
        integers = [x // first if x % first == 0 else x for x in integers]
    return lcm

least_common_multiple = calculate_least_common_multiple()
print(least_common_multiple)

É importante destacar que essa implementação é mais lenta por usar diversas vezes operações de lista. Porém, é um algoritmo didático que facilita o entendimento do que está sendo feito na implementação apresentada pelo Edmar.

comentou Dez 9, 2016 por Edmar Rocha Pereira (21 pontos)  
Obrigado Cauê pelas dicas e recomendações! Acho que agora está mais claro o código.
Sou iniciante em Python, em Latex e neste forum! Mas com certeza são ferramentas para expandir o conhecimento da nossa turma e de futuras gerações.
...