Utilizando os conceitos de procedimentos e funções, desenvolva um algoritmo que, dado um conjunto de N pares de números inteiros positivos, imprima aqueles pares que são formados por números “amigos”.
Obs: 2 números inteiros são considerados “amigos” se cada um for igual a soma dos divisores do outro, incluindo o 1 e excluindo ele próprio.

Passo 1

Resumo do problema: precisamos, para um dado número de pares de inteiros positivos, identificar e imprimir só aqueles pares que são formados por números “amigos” (dois números são amigos se cada um for igual à soma dos divisores próprios do outro). Vamos usar funções para modularizar o cálculo da soma de divisores e um procedimento principal para ler os dados e imprimir o resultado.

Passo 2

Definir uma função sumDivisores(n) que retorna a soma dos divisores próprios de n (ou seja, todos divisores positivos de n, excluindo n). A ideia é: iniciar soma em 1, percorrer i de 2 até √n, se i divide n somar i e somar n/i quando for diferente de i. Por fim, retornar essa soma.

Passo 3

Definir uma função sãoAmigos(a, b) que use sumDivisores para testar se a soma dos divisores de a é b e a soma dos divisores de b é a. Retornar verdadeiro se ambos os testes passarem.

Passo 4

Implementar o procedimento principal main(). Nele, ler o inteiro N (quantidade de pares), depois em loop de 1 até N ler cada par (a, b). Para cada par, chamar sãoAmigos(a, b) e, se verdadeiro, imprimir o par como amigável.

Passo 5

Testar o algoritmo com exemplos conhecidos, por exemplo (220, 284) deve ser impresso, enquanto (10, 20) não.

Passo 6

Complexidade e observações: a função sumDivisores gasta O(√n) para um n, e no pior caso executamos essa função duas vezes por par. Para N pares e valores limitados, o algoritmo é viável.

Resposta

Pseudocódigo do algoritmo usando procedimentos e funções:
function sumDivisores(n: inteiro): inteiro
// Retorna soma dos divisores próprios de n
soma ← 1
limite ← ⌊√n⌋
for i de 2 até limite faça
if n mod i = 0 então
soma ← soma + i
if i <> (n ÷ i) então
soma ← soma + (n ÷ i)
fim se
fim se
fim para
return soma
end function
function sãoAmigos(a: inteiro, b: inteiro): booleano
// Dois números são amigos se cada um é a soma dos divisores do outro
return (sumDivisores(a) = b) e (sumDivisores(b) = a)
end function
procedure main()
leia N // número de pares
for k de 1 até N faça
leia a, b
if sãoAmigos(a, b) então
escreva(a, ", ", b)
fim se
fim para
end procedure
// Chamada do programa
main()

Exercícios relacionados