Números Amigos Escreva um programa que receba dois números inteiros positivos e determine se eles são “Amigos”. Dois números são amigos se a soma dos divisores próprios de um (excluindo o próprio número) for igual ao outro e vice-versa.
Exemplo: 220 e 284 são amigos.
- Divisores de 220:
(Soma
).
- Divisores de 284: 1, 2, 4, 71,
Soma
.
Exemplo: 220 e 284 são amigos.
Passo 1
O enunciado pede um programa que receba dois números inteiros positivos e determine se eles são “Amigos”.
O que exatamente é pedido:
O que exatamente é pedido:
- Entrada: dois inteiros positivos (digamos
e ). - Saída: indicar se
e são amigos, isto é, se a soma dos divisores próprios de (excluindo mesmo) é igual a e, simultaneamente, a soma dos divisores próprios de é igual a .
Informações importantes que o enunciado dá (explícitas ou implícitas):
- Exemplo clássico:
e são amigos porque a soma dos divisores próprios de é e a soma dos divisores próprios de é . - Precisamos calcular a soma dos divisores próprios de um número de forma eficiente para usar no programa.
Passo 2
Entender o que são divisores próprios e como somá-los sem desperdiçar tempo.
Definição: os divisores próprios de um número são todos os inteiros positivos que dividem
sem resto, exceto o próprio
. Por exemplo, para
os divisores próprios são
.
Definição: os divisores próprios de um número
Estratégia direta (ingênua): somar todos os
de
até
que dividem
. Isso funciona, mas custa tempo
por número — lento se os números são grandes.
Melhor estratégia (a que vamos usar): usar o fato de que divisores aparecem em pares. Se
divide
e
, então existe
que também divide
. Portanto, basta testar
até
e, quando
divide
, adicionar tanto
quanto
(quando diferentes). Isso dá custo
.
Importante: como queremos divisores próprios, precisamos garantir que o próprio
não seja somado. Uma forma simples de implementar:
- Se
então soma dos divisores próprios é . - Se
, inicializar a soma com (porque sempre é divisor próprio) e verificar divisores de até . Quando divide , somar e o par (se for diferente de ). Nunca somar porque: - Quando
o par seria , mas já inicializamos com e não adicionamos o par . - Nos testes de
, será menor que (exceto quando que já tratamos).
- Quando
Passo 3
Detalhamento do algoritmo para somar divisores próprios de
(implementável numa prova ou num programa):
- Se
então retornar . - Inicializar
. - Para cada inteiro
tal que : - Se
divide (ou seja, ): - Calcular
. - Se
então adicionar a . - Se
(ou seja, é raiz quadrada exata de ) então adicionar apenas (para não duplicar).
- Calcular
- Se
- Retornar
.
Por que isso exclui
? Porque:
- Não adicionamos
quando inicializamos com e só testamos , e será igual a somente quando que não faz parte do laço.
Complexidade: cada chamada leva tempo proporcional a
, ou seja,
.
Passo 4
Casos especiais e cuidados que devo mencionar (úteis na prova e na implementação):
-
: soma dos divisores próprios é . -
primo: soma será . -
quadrado perfeito: quando precisa adicionar apenas uma vez. - Entradas grandes: o método acima é suficientemente rápido para muitos casos práticos, pois testa até
.
Passo 5
Como decidir se dois números
e
são amigos usando a função acima:
- Calcular
= soma dos divisores próprios de . - Calcular
= soma dos divisores próprios de . -
e são amigos se, e somente se, e .
No tempo de prova, implemente duas chamadas da função de soma e compare. É direto.
Passo 6
Exemplo manual (para ficar seguro):
.
-
. Testar a . - Quando
: → adicionar .
Quando: → adicionar .
E assim por diante até somar todos os pares; contandono começo obtemos finalmente .
Agora: - Repetindo, obtemos
.
Portantoe satisfazem e : são amigos.
Passo 7
Dicas práticas para implementação e teste rápido no computador:
- Ler dois inteiros da entrada padrão; aceitar tanto na mesma linha quanto em linhas diferentes.
- Tratar possíveis espaços extras usando leitura com split.
- Imprimir exatamente uma linha com algo claro como “Sao amigos” ou “Nao sao amigos”.
- Testar com o par
e também com pares óbvios que não são amigos (por exemplo ).
Passo 8
Pronto — abaixo está o programa em Python que implementa tudo o que expliquei (leitura, função eficiente de soma de divisores próprios, verificação e saída). Este é o resultado final que podes colar e executar.
Resposta
import sys
def sum_proper_divisors(n):
if n == 1:
return 0
s = 1
i = 2
while i * i <= n:
if n % i == 0:
j = n // i
if j != i:
s += i + j
else:
s += i
i += 1
return s
if n == 1:
return 0
s = 1
i = 2
while i * i <= n:
if n % i == 0:
j = n // i
if j != i:
s += i + j
else:
s += i
i += 1
return s
def main():
data = sys.stdin.read().strip().split()
if len(data) < 2:
return
a = int(data[0])
b = int(data[1])
if sum_proper_divisors(a) == b and sum_proper_divisors(b) == a:
print(“Sao amigos”)
else:
print(“Nao sao amigos”)
data = sys.stdin.read().strip().split()
if len(data) < 2:
return
a = int(data[0])
b = int(data[1])
if sum_proper_divisors(a) == b and sum_proper_divisors(b) == a:
print(“Sao amigos”)
else:
print(“Nao sao amigos”)
if name == “main”:
main()
main()