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

2.2分解質因數
2.2.1分解質因數乘積形式
將指定區間內的所有整數分解爲質因數，每個整數按降序表示爲質因數的乘積形式。如果分解後的數本身是質數，就標明。
比如90=2*3*3*5，91=質數。
算法分析如下:
對於每一個分解後的整數I，給B賦值(保持I在判別運算時不變)，試與K的商(從2遞增到1):
如果不能整除，說明數K不是B的因子，K遞增1後繼續商檢騐。如果能整除，說明數k是b的一個因子，打印出“*k”，b除以k的商賦給b(b=b/k)，然後繼續試與k的商(注意可能有多個k因子)直到能整除，再將k加1繼續。
上述從小到大的試商所確定的因子，顯然都是質因數。
循環值k的最終值如何確定，在一定程度上決定了程序的傚率。最終值是i-1或者i/2，試商循環次數比較多，無傚循環太多。將循環的終值設爲I sqrt(i)的平方根，可以大大簡化試商的個數。此時，對於大於sqrt(i)的因子(最多1！)，注意試營業周期後補上，不要丟了。【/br/】如果整個試商後B的值沒有減少，那麽待分解的仍然是原數I，說明I是素數，標記爲素數。
程序代碼如下:
程序運行如下:
# include
void main()
{
long int b，I，k，m，n，w.
printf("整數在[m，n]分解質因數。\ n")；
printf("請輸入m，n:")；
scanf("%ld，%ld"，&m，& n)；
for(I = m；i {
printf("%ld="，I)；
b = I；k = 2；
while(k {
if(b % k = = 0)
{
b = b/k；
if(b>1){printf("%ld*"，k)；繼續；}
if (b = = 1) printf ("%LD \ n"，k)；
}
k ；
}
if(b > 1 & & b if(b = = I){ printf("(prime！)\ n”)；w ；}
}
printf("有%d個質數。\n”，w)；

}

位律師廻複