Repetição

[thorsen09]

Madame Rachel possui uma mansão onde ela recebe todos os seus descendentes (netos e bisnetos) durante as férias. Sua mansão possui exatamente N quartos (cada quarto é numerado de 1 a N), onde N é também a quantidade de netos e bisnetos (cada descendente é também numerado de 1 a N). Como toda criança, os descendentes de Madame Rachel são bastante travessos. Todo dia sempre fazem a mesma brincadeira: eles acordam de manhã cedo antes dela e se encontram no grande jardim. Cada descendente, um de cada vez, entra na mansão e troca o estado das portas dos quartos cujos números são múltiplos do seu identificador. Trocar o estado de uma porta significa fechar uma porta que estava aberta ou abrir uma porta que estava fechada. Por exemplo, o descendente cujo identificador é igual a 15 vai trocar o estado das portas 15, 30, 45, etc. Considerando que todas as portas estão inicialmente fechadas (todos os descendentes fecham as portas antes de descer para o jardim) e que cada descendente entra exatamente uma vez na mansão em uma ordem completamente aleatória, quais portas estarão abertas após a entrada de todos os descendentes na mansão?

Entrada vai ser o numero de quartos (e tmb descendentes)
Saida vai ser todas as portas que estarão abertas 

EX: 
6 
1 4

Como faço isso? Eu não postei o código por que eu não consegui entender isso direito, digo como montar essa estrutura de repetição.

[Hazzu]

Como todo descendente alterará o estado de todas as portas nais quais são múltiplas de seu identificador, as portas terão seus estado alterado div vezes, onde div é o número de divisores da porta. De fato, a porta 8 por exemplo, terá seu estado alterado 4 vezes, pelos descendentes 1, 2, 4 e 8 (divisores de 8). Desta forma, basta calcular a quantidade de divisores da porta para saber quantas vezes teve seu estado alterado e descobrir seu estado atual, visto que é dado o estado inicial (fechada). Repare que após uma quantidade par de mudança de estado, a porta sempre voltará a ficar fechada e, quando ímpar, esta estará aberta. Vamos ao código:

//Programa: Portas Madame Rachel
//Função: Calcular quais portas ficarão abertas na mansão da Madame Rachel
//Autor: Hazzu#7444
//Data: 15/06/2020

//Cabeçalhos
#include <stdio.h>
#include <locale.h>


//Função principal
int main(){
    //Declaração de variáveis
    int q, i, n, div;
    
    setlocale(LC_ALL, "Portuguese");    //Configurando terminal para português
	
	//Apresentação
	printf("------ Portas Madame Rachel ------\n");
	printf("Olá, esse programa irá calcular quais portas ficarão abertas na mansão da Madame Rachel.\n");

	//Solicitando número
	printf("-Digite a quantidade de quartos:\n");
	scanf("%d", &n);
	
    //Avaliando estado final
	printf("Portas que ficarão abertas:\n");
	for (q=1; q<=n; q++){	//Percorrendo quartos
		div = 0;
		for (i=1; i<=q; i++){		//Calculando numero de alterações de estado (divisores)
			if (q % i == 0) div++;
		}
		if (div % 2 == 1) printf("%d\n", q);
	}
	
    //Encerrando programa
	printf("Obrigado por utilizar o programa!\n");
    return 0;
}

Um fato curioso que você pode notar ao inserir um alto valor para n é que todos os números são quadrados perfeitos. Isto ocorre porque todos números naturais com uma quantidade ímpar de divisores são quadrados perfeitos. De fato, como é demonstrado aqui. Sabendo disto, podemos otimizar nosso algorítimo imprimindo apenas os quadrados perfeitos de 1 a n. Vamos ao código:
 

//Programa: Portas Madame Rachel
//Função: Calcular quais portas ficarão abertas na mansão da Madame Rachel
//Autor: Hazzu#7444
//Data: 20/06/2020

//Cabeçalhos
#include <stdio.h>
#include <locale.h>


//Função principal
int main(){
    //Declaração de variáveis
    int r, n;
    
    setlocale(LC_ALL, "Portuguese");    //Configurando terminal para português
	
	//Apresentação
	printf("------ Portas Madame Rachel ------\n");
	printf("Olá, esse programa irá calcular quais portas ficarão abertas na mansão da Madame Rachel.\n");

	//Solicitando número
	printf("-Digite a quantidade de quartos:\n");
	scanf("%d", &n);
	
    //Avaliando estado final
	printf("Portas que ficarão abertas:\n");
	for (r = 1; r*r <= n; r++){	//Percorrendo raízes
		printf("%d ", r*r);
	}
	
    //Encerrando programa
	printf("\n\nObrigado por utilizar o programa!");
    return 0;
}

Você pode comprovar a diferença gritante de eficiência ao informar o valor 999999999 para n às duas versões.

Editado Junho 20, 2020 por Hazzu