C語言經典算法：如何較快的分解質因數

將一個正整數分解質因數。例如：輸入90,打印出90=2*3*3*5。

初級算法：

2. #include<stdio.h>   
4. #include<stdlib.h>   
5. #include<math.h>   
6. int main()  
7. {  
8.         int n,i;  
9.         scanf("%d",&n);  
10.         printf("%d=",n);  
11.         for(i=2;i<=sqrt(n);i++)  
12.         {  
13.            if(n%i==0)  
14.            {  
15.               n/=i;  
16.               printf("%d*",i--);  
17.        }  
18.          }  
19.        printf("%d\n",n);  
20.         system("pause");  
21.         return 0;  
22. } 

改進版：

1. #include<stdio.h>   
2. #include<stdlib.h>   
3. #include<math.h>   
4. int main()  
5. {  
6.         int n,i;  
7.         scanf("%d",&n);  
8.         printf("%d=",n);  
9.         while(n%2==0){  
10.                                     printf("%d*",2);  
11.                                     n/=2;  
12.                                     }  
13.         for(i=3;i<=sqrt(n);i+=2)  
14.         {  
15.            if(n%i==0)  
16.            {  
17.               n/=i;  
18.               printf("%d*",i);  
19.               i-=2;  
20.        }  
21.          }  
22.        printf("%d\n",n);  
23.            
24.         system("pause");  
25.         return 0;  
26. }  

因為在所以的質數中只有2是偶數外，其他的質數都是奇數。所以i可以一次+2跳過所有的偶數。不過2要特別處理。

待續未完。相信還有更好的算法。