/**********************************************************/

1. #include<stdio.h>      
2. #include<stdlib.h>   
3. #include<string.h>   
4. #include<math.h>   
5. int gcd(int a,int b)   
6.  {   
7.   int temp;   
8.   while(a%b)         
9.    {         
10.     temp=a;         
11.     a=b;         
12.     b=temp%b;                    
13.    }   
14.    return b;   
15.  }   
16.   int time[10000001]={0};           /*計錄素勾股數個數*/  
17. int main()                          /*先建立資料庫*/    
18. {   
19.   int n,m,c;                        /*n m為下面公式所建立的*/  
20.     for(n=1;n<2237;n++)             

       /*計算個別素勾股數個數 n的平方只要跑到5000000即可*/      

1.     {   
2.         for(m=n+1;m<3163;m=m+2)     

       /*處理的順序很重要3163的平方 最接近100000000*/  

1.         {   
2.          if (gcd(m,n)>1) continue;  /*不互質則跳過 */  
3.           c=m*m+n*n;   
4.          if(c>=10000001) break;   
5.           time[c]++;   
6.         }   
7.     }        
8.   for (c=1;c<10000001;c++)         /*加總*/     
9.    time[c]=time[c]+time[c-1];      /*形成資料庫*/  
10.   while (scanf("%d",&c)==1&&c!=0)   
11.   {   
12.     printf("%d\n",time[c]);   
13.   }   
14.    return 0;   
15. }   
16. /*利用此一性質，計算所有斜邊小於10000000的素勾股數，*/  
17. /* abc為三邊  m > n 、 m 和 n 均是正整*/  
18. /*a = m^2 -n^2, */  
19. /*b = 2mn, */  
20. /*c = m^2+n^2*/