C趣味程序(二)(12)求4位以內(nèi)的相親數(shù)

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