IPython Notebook

MAC2166 - Introdução à Computação

14/04/2014 - Aula 6

Problema 10

Dado um número inteiro n, n>0, verificar se n é primo.

Obs.: Este problema corresponde ao exercício 11 da lista de exercícios sobre inteiros.

Solução 1 (usando uma variável (booleana) indicadora de passagem)

In [ ]:
 
# leia o valor de n
n = int(input("Digite o valor de n (n > 0): "))
 
# n é primo até que se prove o contrário
é_primo = True
 
# procure por um divisor de n entre 2 e n-1
divisor = 2
while divisor < n and é_primo: # equivalente a "div... and é_primo == True:"
    if n % divisor == 0:
        é_primo = False
    divisor += 1
  
    
if é_primo and n != 1: # 1 não é primo
    print(n, "é primo")
else:
    print(n, "não é primo")

É importante lembrar que um número inteiro é primo se ele é maior do que 1 e seus únicos divisores são ele mesmo e 1. Assim, 1 não é primo.

Solução 2 (contando os divisores de n entre 1 e n)

In [ ]:
 
# leia o valor de n
n = int(input("Digite o valor de n (n > 0): "))
 
# inicialize o contador de número de divisores de n
cont_divisores = 0
 
# conta o número de divisores entre 1 e n
for divisor in range(1,n+1):
    if n % divisor == 0:
        cont_divisores += 1 
 
# imprima mensagem
if cont_divisores == 2:
    print(n, "é primo")
else:
    print(n, "não é primo")

Na solução acima, é importante observarmos dois comandos que apareceram de forma um pouco diferente do que vínhamos usando em exercícios anteriores:

i) for divisor in range(1,n+1):

Vimos em outras aulas que ao usar o for i in range(n), criamos um laço que executa exatamente n vezes, com i assumindo o valor inicial zero. Na última execução do laço, i vale n-1.

Entretanto, no for acima, a função range recebe dois valores. range(i,f) representa o seguinte intervalo de valores: [i, f[ (ou seja, os valores entre i e f, incluindo o valor i, mas excluindo o valor f. Portanto, o laço for usado na solução acima é executado (n+1)-1 = n vezes, sendo que a variável divisor assume na primeira execução do laço o valor 1 e a cada execução do laço é incrementada em 1. Na última execução do laço, divisor valerá n.

ii) cont_divisores += 1

Esse comando equivale ao comando a seguir:

cont_divisores = cont_divisores + 1

Ou seja, o operador += faz duas operações: ele soma o valor à direita ao valor da variável à esquerda e depois atribui o resultado da soma à variável.

Os operadores -=, *=, //=, /=, **= e %= funcionam de modo análogo. Veja os exemplos a seguir:

In [1]:
 
i = 10
i += 1
print(i)
i *= 10
print(i)
i //= 5
print(i)
i **= 2
print(i)
11
110
22
484

Problema 11

Dado um número inteiro n, n>1, imprimir sua decomposição em fatores primos, indicando também a mutiplicidade de cada fator. Por exemplo, para n=600, a saída deverá ser: fator 2 multiplicidade 3 fator 3 multiplicidade 1 fator 5 multiplicidade 2

Obs.: Este problema corresponde ao exercício 6 da lista de exercícios repetições encaixadas.

In [ ]:
 
n = int(input("Entre com o numero (> 1) a ser decomposto: "))
print("Decomposicao de %d em fatores primos:" %(n))  
 
fator = 2
while n > 1:
    mult = 0
    while n % fator == 0:
        mult += 1
        n = n // fator
        
    if mult != 0:
        print("  fator %d multiplicidade %d" %(fator, mult)) 
    fator += 1

Problema 12

Dados um número inteiro n>0 e uma sequência com n números inteiros maiores do que zero, determinar o máximo divisor comum entre eles.

Por exemplo, para a sequência

3
42 30 105

o seu programa deve escrever o número 3.

Obs.: Este problema corresponde ao exercício 7 da lista de exercícios repetições encaixadas.

Solução 1

In [ ]:
 
n = int(input("Digite a quantidade de números da sequência: "))
novo_mdc = mdc = int(input("Digite um número da sequência: "))
for cont in range(1,n):
    num = int(input("Digite um número da sequência: "))
    divisor = 1
    while divisor <= mdc and divisor <= num:
        if mdc % divisor == 0 and num % divisor == 0:
            novo_mdc = divisor
        divisor += 1
    mdc = novo_mdc
    
print("O MDC dos numeros é ", mdc)

A Solução 1 usa a igualdade mdc(a,b,c) == mdc(mdc(a,b),c).

Em cada iteração, o mdc de dois números, digamos num1 e num2, é encontrado examinando-se os números 1, 2, 3, ..., min(num1,num2) nessa ordem.

Solução 2

In [ ]:
 
n = int(input("Digite a quantidade de números da sequência: "))
mdc = int(input("Digite um número da sequência: "))
for cont in range(1,n):
    num = int(input("Digite um número da sequência: "))
    divisor = mdc
    while mdc % divisor != 0 or num % divisor != 0:
            divisor = divisor - 1
    mdc = divisor
    
print("O MDC dos numeros é ", mdc)

A Solução 2 também usa a igualdade mdc(a,b,c) == mdc(mdc(a,b),c).

Entretanto, em cada iteração o mdc de dois números, digamos num1 e num2, é encontrado examinando-se os números num1, num1-1, num1-2, ..., 2, 1 nessa ordem.

Solução 3 (com uma pequena melhoria com relação à solução anterior)

In [ ]:
 
n = int(input("Digite a quantidade de números da sequência: "))
mdc = int(input("Digite um número da sequência: "))
for cont in range(1,n):
    num = int(input("Digite um número da sequência: "))
 
    if mdc < num:
        divisor = mdc
    else:
        divisor = num
        
    while mdc % divisor != 0 or num % divisor != 0:
            divisor = divisor - 1
    mdc = divisor
    
print("O MDC dos numeros é ", mdc)

Problema Extra

Dados um número inteiro n, n>0, e uma sequência com n números inteiros maiores do que zero, determinar o fatorial de cada número da sequência.

In [ ]:
 
n = int(input("Digite a quantidade de números da sequência "))
 
for cont in range(n):
    copia = num = int(input("Digite um número da sequência: "))
    fat = 1
    while num > 1:   
        fat *= num
        num -= 1
    print("%d! = %d" %(copia,fat))

Tópicos vistos na Aula 6

  • Mais exercícios envolvendo laços com indicador de passagem
  • Exercícios com laços aninhados

Referências e outros materiais para estudo