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: 1,2,4,5,10,11,20,22,44,55,110 (Soma =284 ).
  • Divisores de 284: 1, 2, 4, 71, 142( Soma =220).

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:
  • Entrada: dois inteiros positivos (digamos (a) e (b)).
  • Saída: indicar se (a) e (b) são amigos, isto é, se a soma dos divisores próprios de (a) (excluindo (a) mesmo) é igual a (b) e, simultaneamente, a soma dos divisores próprios de (b) é igual a (a).
Informações importantes que o enunciado dá (explícitas ou implícitas):
  • Exemplo clássico: (220) e (284) são amigos porque a soma dos divisores próprios de (220) é (284) e a soma dos divisores próprios de (284) é (220).
  • 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 n são todos os inteiros positivos que dividem n sem resto, exceto o próprio n. Por exemplo, para n=12 os divisores próprios são 1,2,3,4,6.
Estratégia direta (ingênua): somar todos os i de 1 até n-1 que dividem n. Isso funciona, mas custa tempo \,O(n)\, 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 i divide n e i\le\sqrt{n}, então existe j=n/i que também divide n. Portanto, basta testar i até \lfloor\sqrt{n}\rfloor e, quando i divide n, adicionar tanto i quanto j (quando diferentes). Isso dá custo \,O(\sqrt{n})\,.
Importante: como queremos divisores próprios, precisamos garantir que o próprio n não seja somado. Uma forma simples de implementar:
  • Se n=1 então soma dos divisores próprios é 0.
  • Se n>1, inicializar a soma com 1 (porque 1 sempre é divisor próprio) e verificar divisores i de 2 até \lfloor\sqrt{n}\rfloor. Quando i divide n, somar i e o par n/i (se for diferente de i). Nunca somar n porque:
    • Quando i=1 o par seria n, mas já inicializamos com 1 e não adicionamos o par n.
    • Nos testes de i\ge2, n/i será menor que n (exceto quando n=1 que já tratamos).

Passo 3

Detalhamento do algoritmo para somar divisores próprios de n (implementável numa prova ou num programa):
  1. Se n=1 então retornar 0.
  2. Inicializar \text{sum}=1.
  3. Para cada inteiro i tal que 2 \le i \le \lfloor\sqrt{n}\rfloor:
    • Se i divide n (ou seja, n \bmod i = 0):
      • Calcular j = n / i.
      • Se j \ne i então adicionar i + j a \text{sum}.
      • Se j = i (ou seja, i é raiz quadrada exata de n) então adicionar apenas i (para não duplicar).
  4. Retornar \text{sum}.
Por que isso exclui n? Porque:
  • Não adicionamos n quando inicializamos com 1 e só testamos i\ge2, e j=n/i será igual a n somente quando i=1 que não faz parte do laço.
Complexidade: cada chamada leva tempo proporcional a \lfloor\sqrt{n}\rfloor, ou seja, \,O(\sqrt{n})\,.

Passo 4

Casos especiais e cuidados que devo mencionar (úteis na prova e na implementação):
  • n=1: soma dos divisores próprios é 0.
  • n primo: soma será 1.
  • n quadrado perfeito: quando i^2=n precisa adicionar i apenas uma vez.
  • Entradas grandes: o método acima é suficientemente rápido para muitos casos práticos, pois testa até \sqrt{n}.

Passo 5

Como decidir se dois números (a) e (b) são amigos usando a função acima:
  • Calcular S(a) = soma dos divisores próprios de a.
  • Calcular S(b) = soma dos divisores próprios de b.
  • a e b são amigos se, e somente se, S(a)=b e S(b)=a.
No tempo de prova, implemente duas chamadas da função de soma e compare. É direto.

Passo 6

Exemplo manual (para ficar seguro): (a)=220.
  • \sqrt{220}\approx 14{,}83. Testar i=2 a 14.
  • Quando i=2: 220/2=110 → adicionar 2+110.
    Quando i=4: 220/4=55 → adicionar 4+55.
    E assim por diante até somar todos os pares; contando 1 no começo obtemos finalmente S(220)=284.
    Agora (b)=284:
  • Repetindo, obtemos S(284)=220.
    Portanto 220 e 284 satisfazem S(220)=284 e S(284)=220: 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 (220,284) e também com pares óbvios que não são amigos (por exemplo (10, 20)).

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
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”)
if name == “main”:
main()

Exercícios relacionados