C语言经典算法：如何较快的分解质因数

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要特别处理。

待续未完。相信还有更好的算法。