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);
24. system("pause");
25. return 0;
26. }

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

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