C Representar um número inteiro por somas de quadrados perfeitos

[Tailí Petry]

Boa noite,

 

Gostaria de um auxílio, meu problema não envolve programação ainda, estou na fase da lógica.

 

O problema é: Preciso achar um meio de representar um número inteiro por somas de quadrados perfeitos, isso é: O numero 55 tem como resultado 4, pois 55 = (1)^2 + (1)^2 + (2)^2 + (7)^2 = 4 quadrados perfeitos utilizados.

 

O que eu pensei: Bom olhando o número 55, conseguimos visualizar que o quadrado mais próximo é 7, pois  7² = 49. Desta forma pensei em decrementar o número até chegar na raiz quadrada exata mais próxima, pois raiz de 49 é 7.  Então teríamos o primeiro quadrado encontrado, após fazer o mesmo procedimento com o resto, o resto é 6, logo a raiz mais próxima será 4 = 2², e encontramos o segundo quadrado,  novamente repetir o processo com o resto, que agora é 2, e como não é uma raiz exata, decrementamos 1, e assim encontramos os dois quadrados faltantes. 

 

Entretanto, acho minha lógica muito lerda, pois em números maiores irei gastar muito tempo decrementando 1, gostaria de saber se alguém tem alguma ideia que possa me auxiliar.

 

< Muito Obrigada  >

[Midori]

Pegue a parte inteira da raiz quadrada e no loop vai acumulando a soma do quadrado desse valor. No caso do 55 p.ex a raiz vai dar 7,4161... Para o próximo número calcule a diferença do número original pela soma. Seguindo com o exemplo do 55, o primeiro número foi o 7 então 7² = 49. A diferença 55 - 49 = 6 então pegue a parte inteira da raiz como no cálculo anterior e vai fazendo assim para os próximos até chegar no total exato.

[Tailí Petry]

@Midori Muito muito obrigada