C趣味程序(二)(12)求4位以內的相親數

2.6 相親數
     2500年前數學大師畢哥達拉斯就發(fā)現，220與284兩數之間存在著微妙的聯系：
     220的真因數之和為：1+2+4+5+10+11+20+22+44+55+110=284
     284的真因數之和為：1+2+4+71+142=220
     畢達哥拉斯把這樣的數對A，B稱為相親數：A的真因數之和為B，而B的真因數之和為A。
     相親數的直接推廣是相親數鏈：呈連環(huán)套形式的多個相親數。例如，A的真因數之和為B，B的真因數之和為C，C的真因數之和為D，最后D的真因數之和又為A，則A，B，C，D稱為一個4環(huán)相親數鏈。
     數學界尋找相親數與相親數鏈，竟相打破相親數記錄的熱情不減。
    2.6.1 求4位以內的相親數
     1.算法分析
     對指定區(qū)間中的每一個整數i應用試商實施窮舉判別。根據相親數的定義，用試商法(i mod j=0)找出i的所有小于i的真因數j，并求出真因數的和s。然后用同樣的方法找出整數s的真因數之和s1。如果有s1=i，則i,s為相親數對。
     為減少試商j循環(huán)次數，注意到數i若為非平方數，它的大于1小于i的因數成對出現，一對中的較小因數要小于i的平方根。若數i愉為整數t的平方，此時t為i的一個因數，而不是一對，因而在和s中減去多加的因數t，這樣試商j循環(huán)只要從2取到i的平方根t=SQR(i)，可大減少j循環(huán)次數?？s減程序的運行時間。最后按規(guī)格打印所找出相親數。
    程序代碼如下：
    /*求4位以內的相親數*/
    #include
    #include
    void main()
    {
     int i,j,s,t,s1;
     for(i=11;i<=9999;i++)
     {
     s=1;t=sqrt(i);
     for(j=2;j<=t;j++) if(i%j==0) s=s+j+i/j;
     if(i==t*t)s-=t; /*求i的真因數之和s*/
     if(i     {
     s1=1;t=sqrt(s);
     for(j=2;j<=t;j++) if(s%j==0) s1=s1+j+s/j;
     if(s==t*t) s1-=t; /*求s的真因數之和s1*/
     if(s1==i)
     {
     printf("相親數：%d,%d\n",i,s);
     printf("%d的真因數之和為：1",i); /*規(guī)格打印相親數*/
     for(j=2;j<=i/2;j++) if(i%j==0) printf("+%d",j);
     printf("=%d\n",s);
     printf("%d的真因數之和為：%d",s,1);
     for(j=2;j<=s/2;j++) if(s%j==0) printf("+%d",j);
     printf("=%d\n",i);
     }
     }
     }
    }