C趣味程序(二)(08)分解質(zhì)因數(shù)乘積形式

2.2 分解質(zhì)因數(shù)
    2.2.1 分解質(zhì)因數(shù)乘積形式
     把指定區(qū)間上的所有整數(shù)分解質(zhì)因數(shù)，每一整數(shù)表示為質(zhì)因數(shù)從小到大順序排列的乘積形式。如果被分解的數(shù)本身是素?cái)?shù)，則予以注明。
     例如，90=2*3*3*5，91=素?cái)?shù)。
    算法分析如下：
     對每一個(gè)被分解的整數(shù)i，賦值給b(以保持判別運(yùn)算過程中i不變)，用k(從2開始遞增1取值)試商：
     若不能整除，說明該數(shù)k不是b的因數(shù),k增1后繼續(xù)試商。若能整除，說明該數(shù)k是b的因數(shù)，打印出"*k"，b除以k的商賦給b(b=b/k)后繼續(xù)用k試商(注意，可能有多個(gè)k因數(shù))，直至不能整除，k增1繼續(xù)。
     按上述從小到大試商確定的因數(shù)顯然為質(zhì)因數(shù)。
     循環(huán)取值k的終值如何時(shí)確定，一定程度上決定了程序的效率。終值定為i-1或i/2，試商循環(huán)次數(shù)都比較大，無效循環(huán)太多。循環(huán)終值定為i的平方根sqrt(i)可大精簡試商次數(shù)，此時(shí)對于大于sqrt(i)的因數(shù)(至多1個(gè)!)，在試商循環(huán)結(jié)束后要注意補(bǔ)上，不要遺失。
     如果整個(gè)試商后b的值沒有任何縮減，仍為原來的待分解數(shù)i，說明i是素?cái)?shù)，作素?cái)?shù)說明標(biāo)記。
    程序代碼如下：
    程序運(yùn)行結(jié)果如下：
    #include
    #include
    void main()
    {
     long int b,i,k,m,n,w=0;
     printf("[m,n]中整數(shù)分解質(zhì)因數(shù).\n");
     printf("請輸入m,n:");
     scanf("%ld,%ld",&m,&n);
     for(i=m;i<=n;i++) /*i為待分解的整數(shù)*/
     {
     printf("%ld=",i);
     b=i;k=2;
     while(k<=sqrt(i)) /*k為試商因數(shù)*/
     {
     if(b%k==0)
     {
     b=b/k;
     if(b>1){printf("%ld*",k);continue;} /*k為質(zhì)因數(shù)，返回再試*/
     if(b==1) printf("%ld\n",k);
     }
     k++;
     }
     if(b>1&&b     if(b==i){printf("(素?cái)?shù)!)\n");w++;} /* b=i,表示i無質(zhì)因數(shù)*/
     }
     printf("其中共%d個(gè)素?cái)?shù).\n",w);
    }