データ構造とアルゴリズムの点灯数

1本の廊下にはn(1≦n≦65535)個の電灯が順番に取り付けられており、最初から最後まで番号1、2、3、...n-1、nである.
各電灯は1つの引張スイッチによって制御される.最初、電灯は全部消していました.
n人の学生が廊下を通った.最初の学生は番号が1の倍数の電灯のスイッチを引いた.
次に2番目の学生は番号が2の倍数の電灯のスイッチを引いた.
次に3番目の学生は番号が3の倍数の電灯のスイッチを引いた.
このように続けて、最後にn番目の学生は番号がnの倍数の電灯のスイッチを引いた.
n人の学生がこの規定に従って歩いた後、廊下に電灯がいくつか点灯していた.
注:電灯の数は学生の数と一致しています.
問題を解く構想の1:まだいくつかの明かりが点灯していることを判断するには、それぞれの明かりが奇数回操作されているのか、偶数回操作されているのかを知る必要があります.
偶数回であれば、そのランプはオフになります.奇数回の場合は点灯します

#include 

#define MAX 65535

int main(int argc, cahr* argv[])
{
	int light_counter[MAX] = {0};
	int light_number = 0;
	int i = 1;
	int j = 1;
	
	//Get the number of times each light is operated
	for(i = 1; i <= MAX; ++i)
	{
		for(j = 1; j <= MAX; ++j)
		{
			if(j % i == 0)
				light_counter[j - 1] += 1;
		}
	}
	
	for(i = 0; i < MAX; ++i)
	{
		if(light_counter[i] % 2 == 1)
			light_number++;
	}
	printf("The number of light on is %d.", light_number);
	return 1;
}

解題構想2:各ランプが操作される回数が奇数であるか偶数であるかを知るには、任意の数mに対して、i*j=mの一対の因子iとjを有することができ、m番号のランプはiとjによって操作される.操作が数回奇数であれば、k*k=mとなる数kが必ず存在する.だからこの問題は1-65535の中で何個のk*kがあることを求めます

#include 

#define MAX 65535

int main(int argc, char* argv[])
{
	int k = 1;
	while(k * k <= MAX)
	{
		k++;
	}
	k -=1;
	printf("The number of light on is %d.", k);
	return 1;
}

明らかに第2の解題構想は第1の解題構想より優れている.