TIOJ 1349 [特別加考題] 平方國的平方幣

四平方合定理：任意數可表a*a + b*b + c*c + d*d
三平方合定理：只要數不是4^a(8*k+7) 就可以表成 a*a + b*b + c*c
二平方合定理：p is prime，p = a*a + b*b if and only if 4|p-1

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<vector>
using namespace std;
bool isq(int n){
    if(n == 1) return true;
    int h = (int)(sqrt(n));
    return h*h == n;
}
vector<int> prime;
bool seive[10000]={0};
int main()
{
    for(int lx = 2;lx < 10000;lx++){
        if(seive[lx] == false){
            prime.push_back(lx);
            for(int ly = 2;ly*lx < 10000;ly++)
                seive[ly*lx] = true;
        }
    }
    int n;
    for(;;){
        scanf("%d", &n);
        if(n == 0) break;
        // check 1
        if(isq(n)){
            puts("1");
            continue;
        }
        int prcn = n;
        while(prcn%2 == 0)
            prcn>>=1;
        if(prcn%4 == 1){
            bool ok2 = true;
            for(int lx = 1;lx < prime.size() and prime[lx] <= prcn and ok2;lx++){
                int cc = 0;
                while(prcn%prime[lx] == 0)
                    cc++, prcn/=prime[lx];
                if(prime[lx]%4 == 3)
                    if(cc%2 != 0)
                        ok2 = false;
            }
            if((prcn != 0) and (prcn%4 == 3))
                ok2 = false;
            if(ok2){
                puts("2");
                continue;
            }
        }
        while(n%4 == 0)
            n /= 4;
        puts( (n%8 == 7)? "4":"3");
    }
    return 0;
}