ACM 10110 Light, more light

TL TL TL TL zzzz。
機車啊，害我想弄一個array把1到65535的次方
放進去。

觀察法：
   1 2 3 4 5 6 7 8 9 10  (燈泡)
1  y y y y y y y y y y 
2  y n y n y n y n y n
3  y n n n y y y n n n
4  y n n y y y y y n n
5  y n n y n y y y n y
6  y n n y n n y y n y
7  y n n y n n n y n y
8  y n n y n n n n n y
9  y n n y n n n n y y
10 y n n y n n n n y n
(次數)

row是次數，
column是燈泡。
求第n次，第n個燈泡是亮還是不亮。
所以1到10的解分別是
1 2 3 4 5 6 7 8 9 10
y n n y n n n n y n
想法很簡單，
判斷第i個燈泡是否有因數。
沒因數 => 質數 => 不亮，
有因數 => 合數，
合數兩種情況，
(1)有單數個因素 => 亮
(2)有雙數個因素 => 不亮

以10為例，
1x10 = 2x5 = 5x2 = 10x1 = 10
1, 2, 5, 10所以不亮。
之後簡化，算到根號n就好，
（因為合數必然是兩個數相乘，
兩者之一必有一數大於等於根號n，另一數小於等於根號n）
所以5, 10都可以去掉，
1必然是因素，也去掉。
剩2，單個，但2表示2x5 = 5x2 = 10。
說是單個，要乘以2，實際上是雙數，
唯一一種例外情況，以16為例，
2, 4，兩個，2x8 = 8x2 = 16，
但4x4 = 4x4 = 16，只能算一個。
得到結論：若根號n為n的因素，只能算一個。
這種情況，就是亮（單數個因素）

再往下推，
所以不管因素有幾個，
如果根號n是因素，那必定是單數個因素，
根號n不是因素，必定是雙數個因數。
這樣就很簡單了，
只要判斷根號n是否為n的因素，
就知道第n個燈泡會不會亮。

但是慢慢算還是會TL的（我就是），
所以要嘛用一個超大的array事先算好1~65535的次方數，
要嘛就用math.h函式庫的sqrt()幫忙算根號n。
機車測資啊……
i用unsigned就好，long long會快一點。

/* ACM 10110
 * mythnc
 * 2011/10/28 11:20:00   
 * run time: 0.032
 */
#include <stdio.h>
#include <math.h>

#define YES 1
#define  NO 0

int factor(double n);

int main(void)
{
    double n;

    while (scanf("%lf", &n)) {
        if (n == 0)
            return 0;
        if (n == 1 || factor(n) == YES)
            printf("yes\n");
        else
            printf("no\n");
    }
}

/* factor: calculate the square root of n is integer or not
 * if is return 1 else return 0 */
int factor(double n)
{
    long long i;

    i = sqrt(n);
    if (i * i == n)
        return YES;
    else
        return NO;
}