摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法:數學解.
畢達哥拉斯跟費瑪...建表唄
勾股數的條件

/* abc為三邊  m > n 、 m 和 n 均是正整*/ 
/*a = m^2 -n^2, */ 
/*b = 2mn, */ 
/*c = m^2+n^2*/

之後再建表搜尋費瑪的...

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

#include<stdio.h>     
#include<stdlib.h>  
int gcd(int a,int b)  
 {  
  int temp;  
  while(a%b)        
   {        
    temp=a;        
    a=b;        
    b=temp%b;                   
   }  
   return b;  
 }  
char flag[10000001]={0};
main()                          
{  
  int nn;
  while (scanf("%d",&nn)==1&&nn!=0)  
  {  
    int ans=0,ans2=0;
    int n,m,a,b,c; 
    for(n=1;n<1000;n++)           
     {
        for(m=n+1;m<1000;m=m+2)           
        {
         if (gcd(m,n)>1) continue; 
          c=m*m+n*n;
         if(c>nn) break;  
          ans++;
          for(a=0;a<nn;a++)
           {
             if(c*a>nn) break;
             flag[a*(m*m+n*n)]=1;
             flag[a*(2*m*n)]=1;
             flag[a*(m*m-n*n)]=1;
           }
        }
     }  
    for(a=1;a<=nn;a++)
     {
      if(flag[a]==1) ans2++;
      flag[a]=0;
     }
     printf("%d %d\n",ans,nn-ans2);
   
  }  
   return 0;  
}    
/* abc為三邊  m > n 、 m 和 n 均是正整*/ 
/*a = m^2 -n^2, */ 
/*b = 2mn, */ 
/*c = m^2+n^2*/